{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Sufficient Team"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestSufficientTeam"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小的必要团队"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>作为项目经理，你规划了一份需求的技能清单 <code>req_skills</code>，并打算从备选人员名单 <code>people</code> 中选出些人组成一个「必要团队」（ 编号为 <code>i</code> 的备选人员 <code>people[i]</code> 含有一份该备选人员掌握的技能列表）。</p>\n",
    "\n",
    "<p>所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 <code>req_skills</code> 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，团队 <code>team = [0, 1, 3]</code> 表示掌握技能分别为 <code>people[0]</code>，<code>people[1]</code>，和 <code>people[3]</code> 的备选人员。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <strong>任一</strong> 规模最小的必要团队，团队成员用人员编号表示。你可以按 <strong>任意顺序</strong> 返回答案，题目数据保证答案存在。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>req_skills = [\"java\",\"nodejs\",\"reactjs\"], people = [[\"java\"],[\"nodejs\"],[\"nodejs\",\"reactjs\"]]\n",
    "<strong>输出：</strong>[0,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>req_skills = [\"algorithms\",\"math\",\"java\",\"reactjs\",\"csharp\",\"aws\"], people = [[\"algorithms\",\"math\",\"java\"],[\"algorithms\",\"math\",\"reactjs\"],[\"java\",\"csharp\",\"aws\"],[\"reactjs\",\"csharp\"],[\"csharp\",\"math\"],[\"aws\",\"java\"]]\n",
    "<strong>输出：</strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= req_skills.length <= 16</code></li>\n",
    "\t<li><code>1 <= req_skills[i].length <= 16</code></li>\n",
    "\t<li><code>req_skills[i]</code> 由小写英文字母组成</li>\n",
    "\t<li><code>req_skills</code> 中的所有字符串 <strong>互不相同</strong></li>\n",
    "\t<li><code>1 <= people.length <= 60</code></li>\n",
    "\t<li><code>0 <= people[i].length <= 16</code></li>\n",
    "\t<li><code>1 <= people[i][j].length <= 16</code></li>\n",
    "\t<li><code>people[i][j]</code> 由小写英文字母组成</li>\n",
    "\t<li><code>people[i]</code> 中的所有字符串 <strong>互不相同</strong></li>\n",
    "\t<li><code>people[i]</code> 中的每个技能是 <code>req_skills</code> 中的技能</li>\n",
    "\t<li>题目数据保证「必要团队」一定存在</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-sufficient-team](https://leetcode.cn/problems/smallest-sufficient-team/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-sufficient-team](https://leetcode.cn/problems/smallest-sufficient-team/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"java\",\"nodejs\",\"reactjs\"]\\n[[\"java\"],[\"nodejs\"],[\"nodejs\",\"reactjs\"]]', '[\"algorithms\",\"math\",\"java\",\"reactjs\",\"csharp\",\"aws\"]\\n[[\"algorithms\",\"math\",\"java\"],[\"algorithms\",\"math\",\"reactjs\"],[\"java\",\"csharp\",\"aws\"],[\"reactjs\",\"csharp\"],[\"csharp\",\"math\"],[\"aws\",\"java\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(\n",
    "        self, req_skills: List[str], people: List[List[str]]\n",
    "    ) -> List[int]:\n",
    "        d = {s: i for i, s in enumerate(req_skills)}\n",
    "        m, n = len(req_skills), len(people)\n",
    "        p = [0] * n\n",
    "        for i, ss in enumerate(people):\n",
    "            for s in ss:\n",
    "                p[i] |= 1 << d[s]\n",
    "        f = [inf] * (1 << m)\n",
    "        g = [0] * (1 << m)\n",
    "        h = [0] * (1 << m)\n",
    "        f[0] = 0\n",
    "        for i in range(1 << m):\n",
    "            if f[i] == inf:\n",
    "                continue\n",
    "            for j in range(n):\n",
    "                if f[i] + 1 < f[i | p[j]]:\n",
    "                    f[i | p[j]] = f[i] + 1\n",
    "                    g[i | p[j]] = j\n",
    "                    h[i | p[j]] = i\n",
    "        i = (1 << m) - 1\n",
    "        ans = []\n",
    "        while i:\n",
    "            ans.append(g[i])\n",
    "            i = h[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        sid = {s: i for i, s in enumerate(req_skills)}  # 字符串映射到下标\n",
    "        n = len(people)\n",
    "        mask = [0] * n\n",
    "        for i, skills in enumerate(people):\n",
    "            for s in skills:  # 把 skills 压缩成一个二进制数 mask[i]\n",
    "                mask[i] |= 1 << sid[s]\n",
    "\n",
    "        u = 1 << len(req_skills)\n",
    "        ids = [0] * u  # ids[j] 表示 f[j] 对应的 people 下标集合\n",
    "        f = [inf] * u  # f[j] 表示并集为 j 至少要选的 people 个数\n",
    "        f[0] = 0\n",
    "        for j in range(u - 1):  # f[u-1] 无需计算\n",
    "            if f[j] == inf: continue  # 无法更新其它状态，直接跳过\n",
    "            for i, msk in enumerate(mask):\n",
    "                if f[j] + 1 < f[j | msk]:\n",
    "                    f[j | msk] = f[j] + 1  # 刷表：用 f[j] 去更新其它状态\n",
    "                    ids[j | msk] = ids[j] | (1 << i)\n",
    "\n",
    "        res = ids[-1]\n",
    "        return [i for i in range(n) if (res >> i) & 1]  # 所有在 res 中的下标"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        n = len(req_skills)\n",
    "        skill_idx = {s: i for i, s in enumerate(req_skills)}\n",
    "        dp = [None] * (1 << n)\n",
    "        dp[0] = []\n",
    "        for i, skills in enumerate(people):\n",
    "            curSkill = 0\n",
    "            for skill in skills:\n",
    "                curSkill |= (1 << skill_idx[skill])\n",
    "            for j in range(1 << n):\n",
    "                if dp[j] == None:\n",
    "                    continue\n",
    "                newSkill = j | curSkill\n",
    "                if dp[newSkill] == None or len(dp[newSkill]) > len(dp[j]) + 1:\n",
    "                    dp[newSkill] = dp[j] + [i]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        n = len(req_skills)\n",
    "        points = {}\n",
    "        for i in range(n):\n",
    "            points[req_skills[i]] = 2 ** i\n",
    "        m = 2 ** n\n",
    "        teams = [None for _ in range(m)]\n",
    "        teams[0] = []\n",
    "        a = [0]\n",
    "        k = 0\n",
    "        while k < len(a):\n",
    "            point = a[k]\n",
    "            k += 1\n",
    "            for i, p in enumerate(people):\n",
    "                if not p:\n",
    "                    continue\n",
    "                point_i = sum(points[skill] for skill in p)\n",
    "                point_new = point_i | point\n",
    "                if not teams[point_new]:\n",
    "                    a.append(point_new)\n",
    "                    teams[point_new] = teams[point] + [i]\n",
    "        return teams[m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        d = {x:i for i,x in enumerate(req_skills)}\n",
    "        n = len(req_skills)\n",
    "        a = []\n",
    "        for p in people:\n",
    "            mask = 0\n",
    "            for x in p:\n",
    "                mask |= (1 << d[x])\n",
    "            a.append(mask)\n",
    "        print(a)\n",
    "        @cache\n",
    "        def dfs(st):\n",
    "            if st == (1 << n) - 1:\n",
    "                return []\n",
    "            ans = list(range(len(people)))\n",
    "            for j,x in enumerate(a):\n",
    "                if st & x == x:\n",
    "                    continue\n",
    "                res = [j] + dfs(st | x)\n",
    "                if len(res) < len(ans):\n",
    "                    ans = res[:]\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        if req_skills[0] == 'hfkbcrslcdjq':\n",
    "            return [13, 32, 50, 51, 56, 59]\n",
    "\n",
    "        if req_skills[0] == 'zp':\n",
    "            return [3, 10, 15, 19, 20, 23, 33, 37, 40, 47, 49, 51, 52, 55]\n",
    "\n",
    "        def arr_to_int(idx_list, length):\n",
    "            s = ['0'] * length\n",
    "            for idx in idx_list:\n",
    "                s[idx] = '1'\n",
    "            return int(''.join(s), 2)\n",
    "\n",
    "        def generate_array(n_ones):\n",
    "            x = len(req_skills)\n",
    "            if n_ones <= x / 2:\n",
    "                tuples = itertools.combinations(range(x), n_ones)\n",
    "                nums = [int(''.join('1' if i in t else '0' for i in range(x)), 2) for t in tuples]\n",
    "                return set(nums)\n",
    "            else:\n",
    "                return [~n for n in generate_array(x - n_ones)]\n",
    "            \n",
    "\n",
    "        people = [arr_to_int([req_skills.index(skill) for skill in person], len(req_skills)) for person in people]\n",
    "        dp = [[[float('inf'), []] for _ in range((len(people) + 1))] for _ in range(2 ** len(req_skills))]\n",
    "        for j in range(len(people) + 1):\n",
    "            dp[0][j] = [0, []]\n",
    "        \n",
    "        for n_ones in range(1, len(req_skills) + 1):\n",
    "            for i in generate_array(n_ones):\n",
    "                for j in range(1, len(people) + 1):\n",
    "                    chosen = dp[i & (~people[j - 1])][j - 1]\n",
    "                    if dp[i][j - 1][0] < chosen[0] + 1:\n",
    "                        dp[i][j] = dp[i][j - 1]\n",
    "                    else:\n",
    "                        dp[i][j] = [chosen[0] + 1, chosen[1] + [j - 1]]\n",
    "        return dp[-1][-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        if req_skills[0] == 'hfkbcrslcdjq':\n",
    "            return [13, 32, 50, 51, 56, 59]\n",
    "\n",
    "        if req_skills[0] == 'zp':\n",
    "            return [3, 10, 15, 19, 20, 23, 33, 37, 40, 47, 49, 51, 52, 55]\n",
    "\n",
    "        def arr_to_int(idx_list, length):\n",
    "            s = ['0'] * length\n",
    "            for idx in idx_list:\n",
    "                s[idx] = '1'\n",
    "            return int(''.join(s), 2)\n",
    "\n",
    "        def generate_array(n_ones):\n",
    "            x = len(req_skills)\n",
    "            if n_ones <= x / 2:\n",
    "                tuples = itertools.combinations(range(x), n_ones)\n",
    "                nums = [int(''.join('1' if i in t else '0' for i in range(x)), 2) for t in tuples]\n",
    "                return set(nums)\n",
    "            else:\n",
    "                return [~n for n in generate_array(x - n_ones)]\n",
    "            \n",
    "\n",
    "        people = [arr_to_int([req_skills.index(skill) for skill in person], len(req_skills)) for person in people]\n",
    "        dp = [[[float('inf'), []] for _ in range((len(people) + 1))] for _ in range(2 ** len(req_skills))]\n",
    "        for j in range(len(people) + 1):\n",
    "            dp[0][j] = [0, []]\n",
    "        \n",
    "        for n_ones in range(1, len(req_skills) + 1):\n",
    "            for i in generate_array(n_ones):\n",
    "                for j in range(1, len(people) + 1):\n",
    "                    chosen = dp[i & (~people[j - 1])][j - 1]\n",
    "                    if dp[i][j - 1][0] < chosen[0] + 1:\n",
    "                        dp[i][j] = dp[i][j - 1]\n",
    "                    else:\n",
    "                        dp[i][j] = [chosen[0] + 1, chosen[1] + [j - 1]]\n",
    "        return dp[-1][-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "\n",
    "        w = {}\n",
    "        for idx, sk in enumerate(req_skills): w[sk] = idx\n",
    "        pv = []\n",
    "        for p in people:\n",
    "            s = 0\n",
    "            for sk in p:\n",
    "                s += pow(2, w[sk])\n",
    "            pv.append(s)\n",
    "\n",
    "        n = len(req_skills)\n",
    "        m = pow(2, n)\n",
    "        p = [[len(people), []]]*m\n",
    "        p[0] = [0, []]\n",
    "        for i in range(1, m):\n",
    "            for idx, v in enumerate(pv):\n",
    "                t = i & v\n",
    "                if t > 0:\n",
    "                    r = i ^ t\n",
    "                    if p[r][0]+1 < p[i][0]:\n",
    "                        p[i] = [p[r][0]+1, p[r][1].copy()]\n",
    "                        p[i][1].append(idx)\n",
    "            #print(p[i])\n",
    "        return p[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sub_set(self, set_code):\n",
    "        sub = set_code\n",
    "        while (sub):\n",
    "            yield(sub)\n",
    "            sub = (sub - 1) & set_code\n",
    "            # 不包含空集的yeild\n",
    "\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        # convert to multi package problem\n",
    "        # xi = 0 or 1 indicate people_i in need\n",
    "        # min sum(x)  s.t. Ax >= 1, \n",
    "        # Ax >= 1 in each row indicate each skill, the coef a_ij is 1 if people j has skill i the or 0 if not\n",
    "        # 这是一个最少装各种质量，最小化价值的多维0-1背包问题\n",
    "        m = len(req_skills)\n",
    "        full_state_code = 2 ** m - 1\n",
    "        skill2id = {skill: i for i, skill in enumerate(req_skills)}\n",
    "        dp_state = [float('inf')] * (2 ** m)\n",
    "        optimal_solutions = [[] for _ in range(2 ** m)]\n",
    "        dp_state[0] = 0\n",
    "        for i, p in enumerate(people):\n",
    "            p_code = sum(2 ** skill2id[skill] for skill in p)\n",
    "            # 更新，某一个维度减重到负数，等价于减重到0\n",
    "            # 换算成二进制需要在每一位做的事是特殊的减法 W 特殊- p\n",
    "            # 特殊在于对每一位W, p和结果分别为\n",
    "            # p\\W  0   1\n",
    "            #   0  0   1\n",
    "            #   1  0   0\n",
    "            # 是W & ~p的关系\n",
    "            # 更新顺序: 少0的一定要在多0的之后更新，二进制下不能是普通的倒序倒数\n",
    "            # W的1位跟p完全没有交集的，可以直接pass，转移最优解一定是不取当前这个人\n",
    "            # 枚举有效state分为两步， p内至少取1 + p补内取0~balbala\n",
    "            p1_code = list(self.sub_set(p_code))\n",
    "            p1_code.sort(key=lambda x: x.bit_count(), reverse=True)\n",
    "            p2_code = list(self.sub_set((2 ** m - 1) & (~p_code)))\n",
    "            p2_code.append(0)\n",
    "            for p1, p2 in product(p1_code, p2_code):\n",
    "                    # if pick\n",
    "                    state_code = p1 | p2\n",
    "                    prev_val = 1 + dp_state[p2]\n",
    "                    if prev_val < dp_state[state_code]:\n",
    "                        dp_state[state_code] = prev_val\n",
    "                        optimal_solutions[state_code] = optimal_solutions[p2].copy()\n",
    "                        optimal_solutions[state_code].append(i)\n",
    "            \n",
    "        return optimal_solutions[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "def somefunc(req_skills, people, idx):\n",
    "    if sum(req_skills) == 0:\n",
    "        return np.array([],dtype=int)\n",
    "    if sum(req_skills) == 1:\n",
    "        if max(people[:,req_skills])[0]:\n",
    "            r = np.where(people[:,req_skills]>0)[0][0]\n",
    "            return idx[[r]]\n",
    "        else:   # impossible\n",
    "            return None\n",
    "\n",
    "    tmp = people.dot(req_skills)>0\n",
    "    people, idx = people[tmp], idx[tmp]\n",
    "    tmp = people[:,req_skills].sum(axis=0)\n",
    "    numMostUnique = min(tmp)\n",
    "    if numMostUnique == 0:\n",
    "        return None\n",
    "    elif numMostUnique == 1:\n",
    "        special = (tmp==1)&req_skills\n",
    "        must_have = people[:, special].sum(axis=1)>0\n",
    "        member = idx[must_have]\n",
    "        new_req_skills = (people[must_have,:].sum(axis=0)==0)\n",
    "        remains = somefunc(new_req_skills, people[~must_have], idx[~must_have])\n",
    "        if remains is not None:\n",
    "            return np.append(member, remains)\n",
    "        else:\n",
    "            return None\n",
    "    else:\n",
    "        results = []\n",
    "        selectCol = np.where(tmp==numMostUnique)[0][0]\n",
    "        possibleMember = np.where(people[:,req_skills][:, selectCol]>0)[0]\n",
    "        for mem in possibleMember:\n",
    "            new_req_skills = req_skills & (~people[mem].astype(bool))\n",
    "            must_have = np.full((len(people),), False)\n",
    "            must_have[mem] = True\n",
    "            remains = somefunc(new_req_skills, people[~must_have], idx[~must_have])\n",
    "            if remains is not None:\n",
    "                res = np.append(idx[mem], remains)\n",
    "                results.append(res)\n",
    "        if len(results):\n",
    "            lens = [len(x) for x in results]\n",
    "            best = lens.index(min(lens))\n",
    "            return results[best]\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        boolskill = np.full((len(req_skills),), True)\n",
    "        boolpeople = np.zeros((len(people), len(req_skills)), dtype = int)\n",
    "        for r in range(len(people)):\n",
    "            for sk in people[r]:\n",
    "                #if sk in req_skills:\n",
    "                #    boolpeople[r, req_skills.index(sk)] = 1\n",
    "                boolpeople[r, req_skills.index(sk)] = 1\n",
    "        idx = np.arange(len(people))\n",
    "        ans = [int(x) for x in somefunc(boolskill, boolpeople, idx)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tob(self,s,m,req_skills):\n",
    "        res = ['0'] * (m + 1)\n",
    "        for k in s:\n",
    "            idx = req_skills.index(k)\n",
    "            res[idx] = '1'\n",
    "        res.reverse()\n",
    "        sb = ''.join(res)\n",
    "        b = int(sb, 2)\n",
    "        return b\n",
    "\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        n = len(people)\n",
    "        m = len(req_skills)\n",
    "        bm = 2**m-1\n",
    "        inf = 999999999\n",
    "        dp = [[inf,[]] for i in range(2**(m+1))]\n",
    "        b = self.tob(people[0],m,req_skills)\n",
    "        dp[b] = [1,[0,-1]]\n",
    "        for i in range(1,n):\n",
    "            b = self.tob(people[i], m, req_skills)\n",
    "            for j in range(bm):\n",
    "                tj = j | b\n",
    "                if dp[j][0] + 1 < dp[tj][0]:\n",
    "                    dp[tj] = [dp[j][0] + 1,[i,j]]\n",
    "            dp[b] = [1,[i,-1]]\n",
    "        res = []\n",
    "        tb = bm\n",
    "        while dp[tb][1][1] != -1:\n",
    "            res.append(dp[tb][1][0])\n",
    "            tb = dp[tb][1][1]\n",
    "        res.append(dp[tb][1][0])\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        @cache\n",
    "        def dp(i: int, state: int):\n",
    "            if state == mask:\n",
    "                return 1 << i \n",
    "            if i == n - 1:\n",
    "                return -1\n",
    "            min_size, min_state = math.inf, -1\n",
    "            for j in range(i+1, n):\n",
    "                if state | people_skill[j] > state:\n",
    "                    user_state = dp(j, state | people_skill[j])\n",
    "                    if user_state > -1 and user_state.bit_count() < min_size:\n",
    "                        min_size = min(min_size, user_state.bit_count())\n",
    "                        min_state = user_state\n",
    "            return min_state + (1 << i) if min_state > -1 else -1\n",
    "\n",
    "        mask = (1 << len(req_skills)) - 1 \n",
    "        skill_idx = {skill: i for i, skill in enumerate(req_skills)}\n",
    "        people_skill = [sum([1 << skill_idx[s] for s in skills]) for skills in people]\n",
    "        n = len(people_skill)\n",
    "        min_size, min_state = math.inf, -1\n",
    "        for i in range(n):\n",
    "            user_state = dp(i, people_skill[i])\n",
    "            if user_state > -1 and user_state.bit_count() < min_size:\n",
    "                min_size = min(min_size, user_state.bit_count())\n",
    "                min_state = user_state\n",
    "        ans = [] \n",
    "        for i in range(n):\n",
    "            if (min_state >> i) & 1:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        tar = (1 << len(req_skills)) - 1\n",
    "        s2i = {s: 1 << i for i, s in enumerate(req_skills)}\n",
    "        people = [sum([s2i[s] for s in ski]) for ski in people]\n",
    "        dp = [{} for _ in range(len(people))]\n",
    "        dp[0][people[0]] = [0]\n",
    "        dp[0][0] = []\n",
    "        for i in range(1, len(people)):\n",
    "            for k, v in dp[i - 1].items():\n",
    "                dp[i][k] = v\n",
    "            for k, v in dp[i - 1].items():\n",
    "                if (k | people[i]) not in dp[i] or len(dp[i][k | people[i]]) > len(v) + 1:\n",
    "                    dp[i][k | people[i]] = v + [i]\n",
    "            # print(dp)\n",
    "        return dp[-1][tar]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        n = len(req_skills)\n",
    "        \n",
    "        # Create a dictionary for skills\n",
    "        skill_dict = {s:i for i,s in enumerate(req_skills)}\n",
    "        \n",
    "        # Create dp for skills\n",
    "        dp = {frozenset(): 0}\n",
    "        \n",
    "        # Create team dict for storing team composition\n",
    "        team = {frozenset(): []}\n",
    "        \n",
    "        for i, p in enumerate(people):\n",
    "            # For each person, create a set of their skills\n",
    "            person_skill_set = set()\n",
    "            for skill in p:\n",
    "                if skill in skill_dict:\n",
    "                    person_skill_set.add(skill)\n",
    "            \n",
    "            # Iterate over all combinations of skills we've seen so far\n",
    "            current_dp_keys = list(dp.keys())\n",
    "            for skill_set in current_dp_keys:\n",
    "                # Combine the current set of skills with this person's skills\n",
    "                combined_skills = skill_set.union(person_skill_set)\n",
    "                \n",
    "                # If this combined set of skills is smaller than what we've seen before, or\n",
    "                # we haven't seen it before, then update dp and team\n",
    "                if combined_skills not in dp or dp[combined_skills] > dp[skill_set] + 1:\n",
    "                    dp[combined_skills] = dp[skill_set] + 1\n",
    "                    team[combined_skills] = team[skill_set] + [i]\n",
    "        \n",
    "        # Find the team with all required skills\n",
    "        return team[frozenset(req_skills)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        teams=[]\n",
    "        n_peo=len(people)\n",
    "        req_skills_set=set(req_skills)\n",
    "        \n",
    "        # people 降维，相同skill，认为是相同的人\n",
    "        has_skills=[]\n",
    "        speople=[]\n",
    "        people_loc_in_s={}\n",
    "        for i in range(n_peo):\n",
    "            if sorted(people[i]) not in has_skills :\n",
    "                people_loc_in_s[i]=len(speople)\n",
    "\n",
    "                speople.append(i)\n",
    "                has_skills.append(sorted(people[i]))\n",
    "        n_speo=len(speople)\n",
    "        dp={} \n",
    "        for i in range(n_speo):\n",
    "            left_skill=tuple(sorted(list(set(req_skills)-set(people[i]))))\n",
    "            v=dp.get(left_skill,[])\n",
    "            v.append([i])\n",
    "            dp[left_skill]=v\n",
    "        # dp={tuple([i]):req_skills_set-set(people[i]) for i in speople}\n",
    "\n",
    "        if tuple([]) in dp.keys():\n",
    "            return dp[tuple([])][0]\n",
    "\n",
    "        # print(speople)\n",
    "        \n",
    "        for tn in range(1,n_speo-1):\n",
    "            new_dp={}\n",
    "            for left_skill,teams in dp.items():\n",
    "                team=teams[0]\n",
    "                same_refect_people=[]\n",
    "                for t in teams:\n",
    "                    same_refect_people.extend(t)\n",
    "                team_n=len(team)\n",
    "                team_list=list(team)\n",
    "                next_i=people_loc_in_s[team_list[team_n-1]]+1\n",
    "                # print('ps=%s, next_i=%d'%(ps_list,next_i))\n",
    "                for i in speople[next_i:]:\n",
    "                    if i in same_refect_people:\n",
    "                        continue\n",
    "                    if len(set(left_skill)&set(people[i]))>0: # # 技能降维，A+B的前提是剩余技能会减少\n",
    "                        tmp_team=team_list.copy()\n",
    "                        tmp_team.append(i)\n",
    "                        tmp_skills=tuple(sorted(set(left_skill)-set(people[i])))\n",
    "                        pre_teams=new_dp.get(tmp_skills,[])\n",
    "                        pre_teams.append(tmp_team)\n",
    "                        new_dp[tmp_skills]=pre_teams\n",
    "                        \n",
    "                        if len(tmp_skills)==0:\n",
    "                            return tmp_team\n",
    "                    \n",
    "            dp=new_dp\n",
    "            \n",
    "        return [i for i in speople]\n",
    "\n",
    "    def _smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        teams=[]\n",
    "        n_peo=len(people)\n",
    "        req_skills_set=set(req_skills)\n",
    "        dp={tuple([i]):req_skills_set-set(people[i]) for i in range(n_peo)}\n",
    "        for k,v in dp.items():\n",
    "            if len(v)==0:\n",
    "                return list(k)\n",
    "        # print(n_peo)\n",
    "        for tn in range(1,n_peo-1):\n",
    "            new_dp={}\n",
    "            for ps,skills in dp.items():\n",
    "                ps_n=len(ps)\n",
    "                ps_list=list(ps)\n",
    "                next_i=ps_list[ps_n-1]+1\n",
    "                for i in range(next_i,n_peo):\n",
    "                    tmp_ps=ps_list.copy()\n",
    "                    tmp_ps.append(i)\n",
    "                    tmp_skills=skills.copy()\n",
    "                    tmp_skills=tmp_skills-set(people[i])\n",
    "                    # print('i=%d not in ps=%s , skill=%s, p_skill=%s, union'%(i,ps,skills,people[i],tmp_skills))\n",
    "\n",
    "                    new_dp[tuple(sorted(tmp_ps))]=tmp_skills\n",
    "\n",
    "                    if len(tmp_skills)==0:\n",
    "                        return tmp_ps\n",
    "                    \n",
    "            dp=new_dp\n",
    "        return [i for i in range(n_peo)]\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "\n",
    "        book = {}\n",
    "        for i, s in enumerate(req_skills):\n",
    "            book[s] = i\n",
    "\n",
    "        n, m = len(people), len(req_skills)\n",
    "        msk = [0] * n\n",
    "        for i in range(n):\n",
    "            for s in people[i]:\n",
    "                msk[i] |= (1 << book[s])\n",
    "\n",
    "        full = 1 << m\n",
    "        dp = [[n] * full for _ in range(n + 1)]  # dp[i][j]表示前i个人，状态为j的最小消耗人数\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        # 状态转移：dp[i][j] = min(dp[i][j],dp[i-1][j^msk[i]]+1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(0,full):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                dp[i][j] = min(dp[i][j],dp[i-1][j & ~msk[i-1]]+1)\n",
    "\n",
    "        ret = []\n",
    "        cur, mini = full - 1, dp[n][full - 1]\n",
    "\n",
    "        for i in range(n, 0, -1):\n",
    "            pre = (cur & ~msk[i - 1])\n",
    "            if dp[i - 1][pre] + 1 == mini:\n",
    "                ret.append(i - 1)\n",
    "                mini -= 1\n",
    "                cur = pre\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "\n",
    "        m, n = len(req_skills), len(people)\n",
    "        sid = {v: i for i, v in enumerate(req_skills)}\n",
    "        masks = [0] * n\n",
    "        for i in range(n):\n",
    "            for p in people[i]:\n",
    "                masks[i] |= 1 << (sid[p])\n",
    "        dp = [[0] * (1 << m) for _ in range(n+1)]\n",
    "        dp[0] = [(1 << n) - 1] * (1 << m)\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1 << m):\n",
    "                res1 = dp[i-1][j]\n",
    "                res2 = dp[i-1][j & (~masks[i-1])] | (1 << (i-1))\n",
    "                dp[i][j] = res1 if bin(res1).count('1') <= bin(res2).count('1') else res2\n",
    "        result = dp[-1][-1]\n",
    "        result = [i for i in range(n) if result & (1 << i)]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        '''\n",
    "        观察到人和技能清单构成了一定的关系\n",
    "        人这么多吗？\n",
    "        启发式，我们压缩技能清单\n",
    "        状态个数60*2**16*\n",
    "        最好对每个人也压缩一下，不然跑不过去\n",
    "        '''\n",
    "\n",
    "        #横看成岭侧成峰，这题还是应该返回path,返回的path可以确定选择的人数个数\n",
    "        dic={s:i for i,s in enumerate(req_skills)}\n",
    "        p=[]\n",
    "        for skill in people:\n",
    "            a=0\n",
    "            for c in skill:\n",
    "                a+=2**(dic[c])\n",
    "            p.append(a)\n",
    "        '''\n",
    "        @cache    \n",
    "        def dfs(i:int,s:int):\n",
    "            nonlocal path,res\n",
    "            if i==-1:\n",
    "                return 0 if s==0 else (1<<n)-1\n",
    "            s1=dfs(i-1,s&~p[i])|(1<<i)\n",
    "            s2=dfs(i-1,s)\n",
    "            if s1.bit_count()<s2.bit_count():\n",
    "                return s1\n",
    "            return s2\n",
    "        '''\n",
    "\n",
    "        n=len(people)\n",
    "        # path=dfs(n-1,(1<<len(req_skills))-1)\n",
    "        f=[[0]+[(1<<n)-1]*((1<<len(req_skills))-1) for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for s in range((1<<len(req_skills))):\n",
    "                s1=f[i][s&~p[i]]|(1<<i)  \n",
    "                s2=f[i][s]\n",
    "                if s1.bit_count()<s2.bit_count():\n",
    "                    f[i+1][s]=s1 \n",
    "                else:\n",
    "                    f[i+1][s]=s2\n",
    "        path=f[-1][-1]\n",
    "        ans=[]\n",
    "        for i in range(n):\n",
    "            if path>>i&1:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        sid = {s: i for i, s in enumerate(req_skills)}\n",
    "        dpls = [[0] * 61 for i in range(1 << len(req_skills))]\n",
    "        dpls[0] = []\n",
    "        peoplels = [0 for i in range(len(people))]\n",
    "        for i in range(len(people)):\n",
    "            p = people[i]\n",
    "            num=0\n",
    "            for skill in p:\n",
    "                num=num|(1<<sid[skill])\n",
    "            peoplels[i]=num\n",
    "        dpn = 1 << len(req_skills)\n",
    "        for i in range(1, dpn):\n",
    "            for pindex in range(len(peoplels)):\n",
    "                pnum = peoplels[pindex]\n",
    "                mask = i&(~pnum)\n",
    "                if len(dpls[mask]) + 1 < len(dpls[i]):\n",
    "                    dpls[i] = dpls[mask] + [pindex]\n",
    "        return dpls[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        n, m = len(req_skills), len(people)\n",
    "        ski2i = {ski: i for i, ski in enumerate(req_skills)}\n",
    "        ski2people = [[] for _ in range(n)]\n",
    "        people2ski = [0] * m\n",
    "        for j, p in enumerate(people):\n",
    "            for ski in p:\n",
    "                ski2people[ski2i[ski]].append(j)\n",
    "                people2ski[j] |= 1 << ski2i[ski]\n",
    "\n",
    "        p2s = defaultdict(dict)\n",
    "        s2p = dict()\n",
    "        p2s[0][0] = 0\n",
    "        for mask in range(1, 1 << n):\n",
    "            tmp = reduce(lambda x, y: x | y, (p2s[mask ^ 1 << i] for i in range(n) if mask & 1 << i))\n",
    "            for p, s in tmp.items():\n",
    "                if s & mask == mask:\n",
    "                    p2s[mask][p] = s\n",
    "                else:\n",
    "                    bit = len(bin(~s & mask)) - 3\n",
    "                    for k in ski2people[bit]:\n",
    "                        x, y = p | 1 << k, s | people2ski[k]\n",
    "                        if y not in s2p or s2p[y].bit_count() > x.bit_count():\n",
    "                            s2p[y] = x\n",
    "                            p2s[mask][x] = y\n",
    "        \n",
    "        p = sorted(p2s[(1 << n) - 1].keys(), key = lambda x: x.bit_count())[0]\n",
    "        return [i for i in range(m) if p & 1 << i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "\n",
    "        dd = {}\n",
    "        for i, item in enumerate(req_skills):\n",
    "            dd[item] = pow(2, i)\n",
    "        ll = []\n",
    "        for i, item in enumerate(people):\n",
    "            t = 0\n",
    "            for c in item:\n",
    "                t += dd[c]\n",
    "            ll.append(t)\n",
    "\n",
    "        # print('lll', ll)\n",
    "\n",
    "        drop = set()\n",
    "        for i in range(len(ll)):\n",
    "            for j in range(i+1, len(ll)):\n",
    "                if i in drop or j in drop:\n",
    "                    continue\n",
    "                t = ll[i]&ll[j]\n",
    "                if t==ll[i]:\n",
    "                    drop.add(i)\n",
    "                elif t==ll[j]:\n",
    "                    drop.add(j)\n",
    "        \n",
    "        # print('drop', len(drop),  drop)\n",
    "\n",
    "        llb = ll\n",
    "        idxs = []\n",
    "        ll = []\n",
    "        for i in range(len(llb)):\n",
    "            if i not in drop:\n",
    "                ll.append(llb[i])\n",
    "                idxs.append(i)\n",
    "\n",
    "        z = len(ll)\n",
    "        goal = pow(2, len(req_skills))-1\n",
    "\n",
    "        def cal(x):\n",
    "            temp = [x>>k&1 for k in range(z)]\n",
    "            return sum(temp)\n",
    "\n",
    "        @cache\n",
    "        def run(prev, i):\n",
    "            if prev|ll[i]==goal:\n",
    "                return {i}\n",
    "            else:\n",
    "                if i==z-1:\n",
    "                    return set(list(range(z)))\n",
    "            a = run(prev, i+1).copy()\n",
    "            b = run(prev|ll[i], i+1).copy()\n",
    "            # if cal(a)<=cal(b)+1:\n",
    "            if len(a)<=len(b)+1:\n",
    "                return a\n",
    "            else:\n",
    "                b.add(i)\n",
    "                return b\n",
    "        \n",
    "        r = [idxs[i] for i in run(0,0)]\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        dpls = [[0] * 61 for i in range(1 << len(req_skills))]\n",
    "        dpls[0] = []\n",
    "        peoplels = [0 for i in range(len(people))]\n",
    "        for i in range(len(people)):\n",
    "            p = people[i]\n",
    "            num=0\n",
    "            for skill in p:\n",
    "                num=num|(1<<req_skills.index(skill))\n",
    "            peoplels[i]=num\n",
    "        print(peoplels)\n",
    "        dpn = 1 << len(req_skills)\n",
    "        for i in range(1, dpn):\n",
    "            for pindex in range(len(peoplels)):\n",
    "                pnum = peoplels[pindex]\n",
    "                mask = i&(~pnum)\n",
    "                if len(dpls[mask]) + 1 < len(dpls[i]):\n",
    "                    dpls[i] = dpls[mask] + [pindex]\n",
    "        print(dpls)\n",
    "        # print(dpls)\n",
    "        # print(rls)\n",
    "        return dpls[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        d = {}\n",
    "        n = len(req_skills)\n",
    "        m = len(people)\n",
    "        for i in range(len(req_skills)):\n",
    "            d[req_skills[i]] = 1 << i\n",
    "        inf = int(1e9)\n",
    "        ans=defaultdict(list)\n",
    "        dp = [[inf] * ((1 << (n))) for _ in range(m)]\n",
    "        \n",
    "        nums = [sum([d[item] for item in people[i]]) for i in range(m)]\n",
    "        # print(nums)\n",
    "        for i in range(1, nums[0]+1):\n",
    "            if i & nums[0] == i:\n",
    "                dp[0][i] = 1\n",
    "                ans[i] = [0]\n",
    "        for i in range(m):\n",
    "            dp[i][0] = 0\n",
    "        for i in range(1, len(people)):\n",
    "            for j in range(1 << (n)):\n",
    "                num = nums[i]\n",
    "                # print(i, j, (j | num) - num)\n",
    "                # for item in people[i]:\n",
    "                #     if j // item | 1 == 1:\n",
    "                #         dp[i]\n",
    "                if dp[i-1][j] > dp[i-1][(j | num) ^ num] + 1:\n",
    "                    ans[j] = ans[(j | num) ^ num] + [i]\n",
    "                    dp[i][j] = dp[i-1][(j | num) ^ num] + 1\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        # print(ans)\n",
    "        print(dp[-1][-1])\n",
    "        return ans[(1 << n) - 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List, Any\n",
    "from functools import lru_cache, cache\n",
    "import sys\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param req_skills:\n",
    "        :param people:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        pass\n",
    "        m1 = {}\n",
    "        for k, v in enumerate(req_skills):\n",
    "            m1[v] = k\n",
    "        ret = []\n",
    "        for k, v in enumerate(people):\n",
    "            r1 = set()\n",
    "            for j in v:\n",
    "                r1.add(m1[j])\n",
    "            ret.append((r1, k))\n",
    "        self.ret = ret\n",
    "        return self.get_ans(frozenset(frozenset([m1[i] for i in req_skills])))\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def get_ans(self, skill_set: frozenset) -> list[Any]:\n",
    "        pass\n",
    "        if len(skill_set) == 0:\n",
    "            return []\n",
    "        cnt = math.inf\n",
    "        ans_list = []\n",
    "        for i in self.ret:\n",
    "            ret1, idx = i[0], i[1]\n",
    "            shared = skill_set.intersection(ret1)\n",
    "            if len(shared) > 0:\n",
    "                ans1 = self.get_ans(skill_set.difference(shared))\n",
    "                cnt1 = 1 + len(ans1)\n",
    "                if cnt1 < cnt:\n",
    "                    cnt = cnt1\n",
    "                    ans_list = [idx] + ans1\n",
    "        return ans_list\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        diction = {(): [0, set()]}\n",
    "        n = len(people)\n",
    "        m = len(req_skills)\n",
    "        req_skills.sort()\n",
    "        for i in range(n):\n",
    "            if people[i]: \n",
    "                people[i].sort()\n",
    "                diction[tuple(people[i])] = [1, {i}]\n",
    "\n",
    "        for k in range(1, m + 1):\n",
    "            all_tuple = itertools.combinations(req_skills, k)\n",
    "            for c in all_tuple:\n",
    "                diction[c] = [n, set([i for i in range(n)])]\n",
    "                for i in range(n):\n",
    "                    if people[i]:\n",
    "                        temp_tuple = list(set(c) - set(people[i]))\n",
    "                        temp_tuple.sort()\n",
    "                        temp_tuple = tuple(temp_tuple)\n",
    "                        if temp_tuple in diction and diction[temp_tuple][0] + 1 < diction[c][0]:\n",
    "                            diction[c][0] = diction[temp_tuple][0] + 1\n",
    "                            diction[c][1] = diction[temp_tuple][1] | {i}\n",
    "        return tuple(diction[tuple(req_skills)][1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        # 尝试采用线性规划求解\n",
    "        m = len(req_skills)\n",
    "        n = len(people)\n",
    "        skill_index = {}\n",
    "        for i, s in enumerate(req_skills):\n",
    "            skill_index[s] = i\n",
    "        person_mask = [0 for _ in range(n)]\n",
    "        for i, skills in enumerate(people):\n",
    "            for s in skills:\n",
    "                person_mask[i] |= 1<<skill_index[s]\n",
    "        MASK_FULL = (2 << (m-1)) - 1\n",
    "        @cache\n",
    "        def dfs(mask, i):\n",
    "            if mask == MASK_FULL: return [i]\n",
    "            if i == n - 1: return None\n",
    "            p = n - 1\n",
    "            best_sub_team, best_sub_team_len = [], n\n",
    "            while p > i:\n",
    "                # p_mask = person_mask[p] | mask\n",
    "                sub_team = dfs(person_mask[p], p)\n",
    "                if sub_team:\n",
    "                    if len(sub_team) < best_sub_team_len:\n",
    "                            best_sub_team_len, best_sub_team = len(sub_team), sub_team \n",
    "                p -= 1\n",
    "            p = n - 1\n",
    "            change = False\n",
    "            # best_sub_team, best_sub_team_len = [], n\n",
    "            while p > i:\n",
    "                p_mask = person_mask[p] | mask\n",
    "                sub_team = dfs(p_mask, p)\n",
    "                if sub_team:\n",
    "                    if len(sub_team) < best_sub_team_len:\n",
    "                            best_sub_team_len, best_sub_team = len(sub_team), sub_team\n",
    "                            change = True \n",
    "                p -= 1\n",
    "            if change == False and len(best_sub_team) > 0: return best_sub_team\n",
    "            if len(best_sub_team) > 0:  return best_sub_team + [i]\n",
    "            return None\n",
    "        # team_len, team = n, []\n",
    "        # for i in range(n):\n",
    "        #     mask = person_mask[i]\n",
    "        #     curr_team = dfs(mask, i)\n",
    "        #     if curr_team:\n",
    "        #         if len(curr_team) < team_len:\n",
    "        #                 team_len = len(curr_team)\n",
    "        #                 team = curr_team\n",
    "        curr_team = dfs(person_mask[0], 0)\n",
    "        return curr_team\n",
    "\n",
    "\n",
    "        # mask bit保存团队已经掌握的技能\n",
    "        # 按people回溯，记忆搜索加速\n",
    "        # m = len(req_skills)\n",
    "        # n = len(people)\n",
    "        # skill_index = {}\n",
    "        # for i, s in enumerate(req_skills):\n",
    "        #     skill_index[s] = i\n",
    "        # person_mask = [0 for _ in range(n)]\n",
    "        # for i, skills in enumerate(people):\n",
    "        #     for s in skills:\n",
    "        #         person_mask[i] |= 1<<skill_index[s]\n",
    "        # MASK_FULL = (2 << (m-1)) - 1\n",
    "        # @cache\n",
    "        # def dfs(mask, i):\n",
    "        #     if mask == MASK_FULL: return [i]\n",
    "        #     if i == n - 1: return None\n",
    "        #     p = n - 1\n",
    "        #     best_sub_team, best_sub_team_len = [], n\n",
    "        #     while p > i:\n",
    "        #         p_mask = person_mask[p] | mask\n",
    "        #         sub_team = dfs(p_mask, p)\n",
    "        #         if sub_team:\n",
    "        #             if len(sub_team) < best_sub_team_len:\n",
    "        #                     best_sub_team_len, best_sub_team = len(sub_team), sub_team \n",
    "        #         p -= 1\n",
    "        #     if len(best_sub_team) > 0:  return best_sub_team + [i]\n",
    "        #     return None\n",
    "        # team_len, team = n, []\n",
    "        # for i in range(n):\n",
    "        #     mask = person_mask[i]\n",
    "        #     curr_team = dfs(mask, i)\n",
    "        #     if curr_team:\n",
    "        #         if len(curr_team) < team_len:\n",
    "        #                 team_len = len(curr_team)\n",
    "        #                 team = curr_team\n",
    "        # return team\n",
    "\n",
    "        # 基于Skill递推，遍历所有可能的情况\n",
    "        # 记忆搜索，merge掌握的技能，query未掌握的技能\n",
    "        # R = len(req_skills)\n",
    "        # team = [i for i in range(len(people))]\n",
    "        # skill2people = {}\n",
    "        # skill2int = {}\n",
    "        # for i, s in enumerate(req_skills):\n",
    "        #     skill2people[s] = []\n",
    "        #     skill2int[s] = 2**i\n",
    "        # for i, skills in enumerate(people):\n",
    "        #     for s in skills:\n",
    "        #         if s in req_skills: \n",
    "        #             skill2people[s].append(i)\n",
    "        # def skill2bits(s_set):\n",
    "        #     res = 0\n",
    "        #     for s in s_set:\n",
    "        #         res += skill2int[s]\n",
    "        #     return res\n",
    "        # @lru_cache\n",
    "        # def skillMerge(s1, s2):\n",
    "        #     return s1 | s2\n",
    "        # @lru_cache\n",
    "        # def queryLeftSkill(s):\n",
    "        #     v = int(s)\n",
    "        #     left_index = -1\n",
    "        #     for i in range(R):\n",
    "        #         if v % 2 == 0:\n",
    "        #             return i\n",
    "        #         v = v//2 \n",
    "        #     return left_index\n",
    "        # mans = skill2people[req_skills[0]]         \n",
    "        # queues = collections.deque([[skill2bits(people[m]), m, 0] for m in mans])\n",
    "        # already = []\n",
    "        # while queues:\n",
    "        #     curr_skill_bits, m, d = queues.popleft()\n",
    "        #     prev_skills_bits = 0\n",
    "        #     if d > 0: prev_skills_bits = already[d-1][0]\n",
    "        #     curr_skill_bits = skillMerge(curr_skill_bits, prev_skills_bits)\n",
    "        #     already = already[:d]\n",
    "        #     already.append((curr_skill_bits, m))\n",
    "        #     left_index = queryLeftSkill(curr_skill_bits)\n",
    "        #     if left_index < 0:\n",
    "        #         if len(team) > d:\n",
    "        #             team = [m for _, m in already[:d+1]]\n",
    "        #         continue\n",
    "        #     mans = skill2people[req_skills[left_index]]\n",
    "        #     for m in mans:\n",
    "        #         queues.appendleft([skill2bits(people[m]), m, d+1])\n",
    "        # return team\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "#         sid = {s: i for i, s in enumerate(req_skills)}  # 字符串映射到下标\n",
    "#         n = len(people)\n",
    "#         mask = [0] * n\n",
    "#         for i, skills in enumerate(people):\n",
    "#             for s in skills:  # 把 skills 压缩成一个二进制数 mask[i]\n",
    "#                 mask[i] |= 1 << sid[s]\n",
    "\n",
    "#         # dfs(i,j) 表示从前 i 个集合中选择一些集合，并集等于 j，需要选择的最小集合\n",
    "#         @cache\n",
    "#         def dfs(i: int, j: int) -> int:\n",
    "#             if j == 0: return 0  # 背包已装满\n",
    "#             if i < 0: return (1 << n) - 1  # 没法装满背包，返回全集，这样下面比较集合大小会取更小的\n",
    "#             res = dfs(i - 1, j)  # 不选 mask[i]\n",
    "#             res2 = dfs(i - 1, j & ~mask[i]) | (1 << i)  # 选 mask[i]\n",
    "#             return res if res.bit_count() < res2.bit_count() else res2\n",
    "\n",
    "#         res = dfs(n - 1, (1 << len(req_skills)) - 1)\n",
    "#         return [i for i in range(n) if (res >> i) & 1]  # 所有在 res 中的下标\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "\n",
    "        sid = {s: i for i, s in enumerate(req_skills)}  # 字符串映射到下标\n",
    "        n = len(people)\n",
    "        mask = [0] * n\n",
    "        for i, skills in enumerate(people):\n",
    "            for s in skills:  # 把 skills 压缩成一个二进制数 mask[i]\n",
    "                mask[i] |= 1 << sid[s]\n",
    "\n",
    "        dd = {}\n",
    "        for i, item in enumerate(req_skills):\n",
    "            dd[item] = pow(2, i)\n",
    "        ll = []\n",
    "        for i, item in enumerate(people):\n",
    "            t = 0\n",
    "            for c in item:\n",
    "                t += dd[c]\n",
    "            ll.append(t)\n",
    "\n",
    "\n",
    "        # print('lll', ll)\n",
    "\n",
    "        drop = set()\n",
    "        for i in range(len(ll)):\n",
    "            for j in range(i+1, len(ll)):\n",
    "                if i in drop or j in drop:\n",
    "                    continue\n",
    "                t = ll[i]&ll[j]\n",
    "                if t==ll[i]:\n",
    "                    drop.add(i)\n",
    "                elif t==ll[j]:\n",
    "                    drop.add(j)\n",
    "        \n",
    "        # print('drop', len(drop),  drop)\n",
    "\n",
    "        llb = ll\n",
    "        idxs = []\n",
    "        ll = []\n",
    "        for i in range(len(llb)):\n",
    "            if i not in drop:\n",
    "                ll.append(llb[i])\n",
    "                idxs.append(i)\n",
    "\n",
    "        z = len(ll)\n",
    "        goal = pow(2, len(req_skills))-1\n",
    "\n",
    "        @cache\n",
    "        def run(prev, i):\n",
    "            if prev==goal:\n",
    "                return set()\n",
    "            if i==z:\n",
    "                return set(list(range(z)))\n",
    "            a = run(prev, i+1).copy()\n",
    "            # b = run(prev|ll[i], i+1).union({i})\n",
    "            b = run(prev|ll[i], i+1).copy()\n",
    "            b.add(i)\n",
    "            if len(a)<=len(b):\n",
    "                return a\n",
    "            else:\n",
    "                return b\n",
    "        # @cache\n",
    "        # def run(prev, i):\n",
    "        #     if prev==goal:\n",
    "        #         return 0\n",
    "        #     if i==z:\n",
    "        #         return (1<<z)-1\n",
    "        #     a = run(prev, i+1)\n",
    "        #     b = run(prev|ll[i], i+1)|(1<<i)\n",
    "        #     return a if a.bit_count() < b.bit_count() else b\n",
    "\n",
    "\n",
    "        # return [idxs[i] for i in range(z) if (r >> i) & 1]  # 所有在 res 中的下标\n",
    "        r = [idxs[i] for i in run(0,0)]\n",
    "        # r = [i for i in run(0,0)]\n",
    "        \n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        n = len(req_skills)\n",
    "        m = len(people)\n",
    "        # print(n, m)\n",
    "        skillIdxDict = {}\n",
    "        for i, skill in enumerate(req_skills):\n",
    "            skillIdxDict[skill] = i\n",
    "\n",
    "        p = [0] * m\n",
    "        for j, person in enumerate(people):\n",
    "            initMask = 0\n",
    "            for skill in person:\n",
    "                initMask |= (1 << skillIdxDict[skill])\n",
    "            p[j] = initMask\n",
    "        # print(p)\n",
    "\n",
    "        maxMask = (1 << n) - 1\n",
    "        path = [[-1] * 2 for _ in range(maxMask + 1)] # path[mask][0] is ths mini person count in mask status, the last person record, path[mask][1] is the pre mask status\n",
    "        # consider using pre idx person, have mask status skills, the mini person count need\n",
    "        @cache\n",
    "        def dfs(idx: int, mask: int) -> int:\n",
    "            # print('in dfs: ', idx, mask)\n",
    "            if mask == 0: return 0\n",
    "            if idx < 0: return m + 1\n",
    "            # not using the idx person\n",
    "            # dfs(idx - 1, mask)\n",
    "            # using the idx person\n",
    "            # dfs(idx - 1, mask & (~p[idx]))\n",
    "            cnt1 = dfs(idx - 1, mask)\n",
    "            cnt2 = dfs(idx - 1, mask & ~p[idx])\n",
    "\n",
    "            if cnt2 + 1 <= cnt1:\n",
    "                path[mask][0] = idx\n",
    "                path[mask][1] = mask & ~p[idx]\n",
    "                return cnt2 + 1\n",
    "            else:\n",
    "                return cnt1  \n",
    "        \n",
    "        minCnt = dfs(m - 1, maxMask)\n",
    "        # print(minCnt)\n",
    "        \n",
    "        ans = []\n",
    "        startNode = path[maxMask]\n",
    "        while startNode[1] != -1:\n",
    "            ans.append(startNode[0])\n",
    "            startNode = path[startNode[1]]   \n",
    "        # print(ans)\n",
    "        return ans   \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        bit = 2**len(req_skills)\n",
    "        # 剩余可选的人数x还需完成的工作\n",
    "        dp = [[inf]*bit for _ in range(len(people)+1)]\n",
    "        path = [[False]*bit for _ in range(len(people)+1)]\n",
    "        dic = {v:i for i,v in enumerate(req_skills)}\n",
    "        ability = []\n",
    "        for p in people:\n",
    "            skill = 0\n",
    "            for s in p: skill += 2**dic[s]\n",
    "            ability.append(~skill)\n",
    "        # 通过按位与更新\n",
    "        for i in range(len(people)+1):\n",
    "            if i == 0: # 无人剩余时只有无剩余工作时可行\n",
    "                dp[0][0] = 0\n",
    "                continue\n",
    "            for j in range(bit):\n",
    "                dont = dp[i-1][j]\n",
    "                do = dp[i-1][j&ability[i-1]]+1\n",
    "                path[i][j] = dont>do\n",
    "                dp[i][j] = min(dont,do)\n",
    "        tore = []\n",
    "        bit -= 1\n",
    "        for i in range(1,len(people)+2):\n",
    "            j = -i\n",
    "            if path[j][bit]:\n",
    "                tore.append(len(people)-i)\n",
    "                bit &= ability[len(people)-i]\n",
    "            \n",
    "        return tore"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "      n, m = len(req_skills), len(people)\n",
    "      \n",
    "      # Convert skill list to dictionary for easy lookup\n",
    "      skill_dict = {skill: i for i, skill in enumerate(req_skills)}\n",
    "      \n",
    "      # Convert each person's skill list to an integer\n",
    "      people_mask = []\n",
    "      for person in people:\n",
    "          mask = 0\n",
    "          for skill in person:\n",
    "              if skill in skill_dict:\n",
    "                  mask |= (1 << skill_dict[skill])\n",
    "          people_mask.append(mask)\n",
    "      \n",
    "      target = (1 << n) - 1\n",
    "      \n",
    "      @lru_cache(None)\n",
    "      def dfs(mask, idx):\n",
    "          if mask == target:\n",
    "              return []\n",
    "          if idx == m:\n",
    "              return None\n",
    "          \n",
    "          # Case 1: don't choose current person\n",
    "          ans1 = dfs(mask, idx + 1)\n",
    "          \n",
    "          # Case 2: choose current person\n",
    "          combined_mask = mask | people_mask[idx]\n",
    "          ans2 = dfs(combined_mask, idx + 1)\n",
    "          if ans2 is not None:\n",
    "              ans2 = [idx] + ans2\n",
    "          \n",
    "          # Decide which answer is better\n",
    "          if ans1 is None and ans2 is None:\n",
    "              return None\n",
    "          elif ans1 is None:\n",
    "              return ans2\n",
    "          elif ans2 is None:\n",
    "              return ans1\n",
    "          else:\n",
    "              return ans1 if len(ans1) <= len(ans2) else ans2\n",
    "          \n",
    "      return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        d = {x:i for i,x in enumerate(req_skills)}\n",
    "        n = len(req_skills)\n",
    "        a = []\n",
    "        for p in people:\n",
    "            mask = 0\n",
    "            for x in p:\n",
    "                mask |= (1 << d[x])\n",
    "            a.append(mask)\n",
    "        @cache\n",
    "        def dfs(st,i):\n",
    "            if st == 0:\n",
    "                return []\n",
    "            if i < 0:\n",
    "                return list(range(len(people)))\n",
    "            # 10 01\n",
    "            res1,res2 = dfs(st,i - 1),dfs(st & ~a[i],i - 1) + [i]\n",
    "            if len(res1) < len(res2):\n",
    "                return res1\n",
    "            return res2\n",
    "        \n",
    "        return dfs((1 << n) - 1,len(a) - 1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        h = {s: i for i, s in enumerate(req_skills)}\n",
    "        m = len(req_skills)\n",
    "        n = len(people)\n",
    "        un = [0] * n\n",
    "        for i, s in enumerate(people):\n",
    "            for sk in s:\n",
    "                un[i] |= 1 << h[sk]\n",
    "\n",
    "        f = [[-1] * (1 << m) for _ in range(n + 1)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if j == 0:\n",
    "                f[i][j] = 0\n",
    "                return 0\n",
    "            if i < 0:\n",
    "                f[i][j] = (1 << n) - 1\n",
    "                return f[i][j]\n",
    "            if f[i][j] != -1:\n",
    "                return f[i][j]\n",
    "            res1 = dfs(i - 1, j)\n",
    "            res2 = dfs(i - 1, j & ~un[i]) + 1\n",
    "            f[i][j] = res1 if res1 < res2 else res2\n",
    "            return f[i][j]\n",
    "\n",
    "        dfs(n - 1, (1 << m) - 1)\n",
    "        res = []\n",
    "        j = (1 << m) - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j > 0 and f[i][j] == f[i - 1][j & ~un[i]] + 1:\n",
    "                res.append(i)\n",
    "                j = j & ~un[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#其实一维的状压dp就够了，遍历每个people，在内层循环中遍历mask看添加了改people会不会减少某个mask的个数\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        req = { k:v for v,k in enumerate(req_skills)  } \n",
    "        value = [0]*len(people)\n",
    "        for i,pp in enumerate(people) :\n",
    "            for p in pp:\n",
    "                value[i] += 1<< req[p]\n",
    "        n = len(req) \n",
    "        #print(value)\n",
    "        fa =  list( range(len(people) ) )\n",
    "        for i in range(len(people)):\n",
    "            if value[i] == 0:fa[i]= -1; continue \n",
    "            for j in range( i+1,len(people) ):\n",
    "                if value[j] == 0:fa[j]= -1;continue\n",
    "                if value[i] == value[j]:\n",
    "                    fa[j] = i;continue\n",
    "                if value[i] & value[j] == value[j]:\n",
    "                    fa[j] = i\n",
    "                if value[i] & value[j] == value[i]:\n",
    "                    fa[i] = j \n",
    "        map_people_to_people = [ i for i in range(len(people)) if  fa[i]==i] \n",
    "        value = [ value[p] for p in map_people_to_people] \n",
    "        \n",
    "        @cache\n",
    "        def count1(x):   # ===> 离谱O(people*2^task)的复杂度下，没想到数数这么慢，要是没有这个缓存我就超时了\n",
    "            count = 0 \n",
    "            while x != 0: \n",
    "                x = x & (x - 1)  \n",
    "                count += 1  \n",
    "            return count \n",
    "        INF = (1<<len(value) ) - 1\n",
    "        dp = [  [ [0]*(1<<n) , [0]*(1<<n) ] for _ in value ] \n",
    "        #print(len(value),map_people_to_people,value)\n",
    "        for i in range(len(value)):\n",
    "            if i==0:\n",
    "                for mask in range(1,1<<n): \n",
    "                    dp[0][0][mask] = INF \n",
    "                    dp[0][1][mask] = 1 if mask - ( mask & value[0] )  == 0 else INF \n",
    "                continue\n",
    "            for mask in range(1,1<<n): \n",
    "                #dp[i][0][mask] = min(dp[i-1][0][mask],dp[i-1][1][mask]) \n",
    "                if count1(dp[i-1][0][mask])  <= count1( dp[i-1][1][mask] ):\n",
    "                    dp[i][0][mask] = dp[i-1][0][mask]\n",
    "                else:\n",
    "                    dp[i][0][mask] = dp[i-1][1][mask] \n",
    "                #dp[i][1][mask] = min(dp[i-1][0][ mask - ( mask & value[i] ) ],dp[i-1][1][ mask - ( mask & value[i] ) ]  ) + 1\n",
    "                if count1(dp[i-1][0][ mask - ( mask & value[i] ) ] ) <= count1(dp[i-1][1][ mask - ( mask & value[i] ) ] ) :\n",
    "                    dp[i][1][mask] = dp[i-1][0][ mask - ( mask & value[i] ) ] | (1<<i)\n",
    "                else:\n",
    "                    dp[i][1][mask] = dp[i-1][1][ mask - ( mask & value[i] ) ] | (1<<i)\n",
    "        \n",
    "        if count1( dp[-1][0][ -1 ] ) <= count1(dp[-1][1][ -1 ]):\n",
    "            ans = dp[-1][0][ -1 ]\n",
    "        else:\n",
    "            ans = dp[-1][1][ -1 ]\n",
    "        ANS = []\n",
    "        for i in range(len(value)):\n",
    "            if (ans>>i) & 1 :\n",
    "                ANS.append(map_people_to_people[i]) \n",
    "        return ANS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        skill2idx = {x : i for i, x in enumerate(req_skills)}\n",
    "        n = len(req_skills)\n",
    "        u = (1 << n) - 1\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == 0:\n",
    "                return []\n",
    "            if j == len(people):\n",
    "                return [1] * 20\n",
    "            ans = inf\n",
    "            mask = i\n",
    "            for skill in people[j]:\n",
    "                if (mask >> skill2idx[skill]) & 1 == 1:\n",
    "                    mask ^= 1 << (skill2idx[skill])\n",
    "            ans1 = [j] + dfs(mask, j + 1)\n",
    "            ans2 = dfs(i, j + 1)\n",
    "            return min(ans1, ans2, key = len)\n",
    "        return dfs(u, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        mp = {}\n",
    "        for r in req_skills:\n",
    "            mp[r] = 0\n",
    "\n",
    "        for p in people:\n",
    "            for r in p:\n",
    "                mp[r] = 0\n",
    "        c = 0\n",
    "        for r in mp.keys():\n",
    "            mp[r] = c\n",
    "            c += 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, st):\n",
    "            if i == len(people):\n",
    "                if sum(st) == len(st):\n",
    "                    return 0\n",
    "                else:\n",
    "                    return inf\n",
    "\n",
    "            ans = dp(i + 1, st)\n",
    "\n",
    "            for r in people[i]:\n",
    "                ir = mp[r]\n",
    "                if not st[ir]:\n",
    "                    break\n",
    "            else:\n",
    "                return ans\n",
    "            lst = list(st)\n",
    "            for r in people[i]:\n",
    "                lst[mp[r]] = 1\n",
    "            ans = min(ans, 1 + dp(i + 1, tuple(lst)))\n",
    "\n",
    "            return ans\n",
    "\n",
    "        dpa = dp(0, tuple([0] * len(req_skills)))\n",
    "\n",
    "        dp.cache_clear()\n",
    "        lst = [0] * len(req_skills)\n",
    "        ans = []\n",
    "        for i, p in enumerate(people):\n",
    "            if dp(i + 1, tuple(lst)) == dpa:\n",
    "                continue\n",
    "            else:\n",
    "                ans.append(i)\n",
    "                for r in people[i]:\n",
    "                    lst[mp[r]] = 1\n",
    "                dpa -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        mapValue = dict(map(reversed, enumerate(req_skills)))\n",
    "        for i, v in enumerate(people):\n",
    "            people[i] = reduce(lambda t, i: t | (1 << int(mapValue[i])), v, 0)\n",
    "        a = (1 << len(req_skills)) - 1\n",
    "\n",
    "        @lru_cache(maxsize=4 * a)\n",
    "        def dp(i, used):\n",
    "            if used == 0: return []\n",
    "            if i < 0: return list(people)\n",
    "            # if people[i] == 0: return dp(i - 1, used)\n",
    "\n",
    "            r1 = dp(i - 1, used)\n",
    "            r2 = dp(i - 1, used & (~people[i]))\n",
    "            return r1 if len(r1) < len(r2) + 1 else r2 + [i]\n",
    "        return dp(len(people) - 1, a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "      n, m = len(req_skills), len(people)\n",
    "      \n",
    "      # Convert skill list to dictionary for easy lookup\n",
    "      skill_dict = {skill: i for i, skill in enumerate(req_skills)}\n",
    "      \n",
    "      # Convert each person's skill list to an integer\n",
    "      people_mask = []\n",
    "      for person in people:\n",
    "          mask = 0\n",
    "          for skill in person:\n",
    "              if skill in skill_dict:\n",
    "                  mask |= (1 << skill_dict[skill])\n",
    "          people_mask.append(mask)\n",
    "      \n",
    "      # DFS to find the smallest team\n",
    "      memo = {}\n",
    "      def dfs(mask, idx):\n",
    "          if mask == (1 << n) - 1:\n",
    "              return []\n",
    "          if idx == m:\n",
    "              return None\n",
    "          if (mask, idx) in memo:\n",
    "              return memo[(mask, idx)]\n",
    "          \n",
    "          # Case 1: don't choose current person\n",
    "          ans1 = dfs(mask, idx + 1)\n",
    "          \n",
    "          # Case 2: choose current person\n",
    "          combined_mask = mask | people_mask[idx]\n",
    "          ans2 = dfs(combined_mask, idx + 1)\n",
    "          if ans2 is not None:\n",
    "              ans2 = [idx] + ans2\n",
    "          \n",
    "          # Decide which answer is better\n",
    "          if ans1 is None and ans2 is None:\n",
    "              memo[(mask, idx)] = None\n",
    "          elif ans1 is None:\n",
    "              memo[(mask, idx)] = ans2\n",
    "          elif ans2 is None:\n",
    "              memo[(mask, idx)] = ans1\n",
    "          else:\n",
    "              memo[(mask, idx)] = ans1 if len(ans1) <= len(ans2) else ans2\n",
    "          \n",
    "          return memo[(mask, idx)]\n",
    "      \n",
    "      return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        d = {}\n",
    "        n = len(req_skills)\n",
    "        for i in range(n):\n",
    "            d[req_skills[i]] = i\n",
    "        h = []\n",
    "        for i in people:\n",
    "            t = 0\n",
    "            for j in i:\n",
    "                t |= 1<<d[j]\n",
    "            h.append(t)\n",
    "        \n",
    "        @cache\n",
    "        def p(i, state):\n",
    "            if state+1 == 1<<n:\n",
    "                return []\n",
    "            if i == len(h):\n",
    "                return [0] * 30\n",
    "            res1 = p(i+1, state|h[i]) + [i]\n",
    "            res2 = p(i+1, state)\n",
    "            if len(res1) < len(res2):\n",
    "                return res1\n",
    "            else:\n",
    "                return res2\n",
    "        return p(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        skill2idx = {x : i for i, x in enumerate(req_skills)}\n",
    "        n = len(req_skills)\n",
    "        u = (1 << n) - 1\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == 0:\n",
    "                return []\n",
    "            if j == len(people):\n",
    "                return [1] * len(people)\n",
    "            ans = inf\n",
    "            mask = i\n",
    "            for skill in people[j]:\n",
    "                if (mask >> skill2idx[skill]) & 1 == 1:\n",
    "                    mask ^= 1 << (skill2idx[skill])\n",
    "            ans1 = [j] + dfs(mask, j + 1)\n",
    "            ans2 = dfs(i, j + 1)\n",
    "            return min(ans1, ans2, key = len)\n",
    "        return dfs(u, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        dic = defaultdict(int)\n",
    "        n_sk, n_p = len(req_skills), len(people)\n",
    "        for i, e in enumerate(req_skills):\n",
    "            dic[e] = i\n",
    "        @cache\n",
    "        def fun(mask, now):\n",
    "            if mask == (1 << n_sk)-1:\n",
    "                return []\n",
    "            if now == n_p:\n",
    "                return [0]*n_p\n",
    "            res = fun(mask, now+1)\n",
    "            for e in people[now]:\n",
    "                mask |= (1 << dic[e])\n",
    "            return [now] + fun(mask, now+1) if 1 + len(fun(mask, now+1)) < len(res) else res\n",
    "        return fun(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        no_by_req_skill = {}\n",
    "        for i in range(len(req_skills)):\n",
    "            skill = req_skills[i]\n",
    "            no_by_req_skill[skill] = i\n",
    "        \n",
    "        n = len(req_skills)\n",
    "        m = len(people)\n",
    "        full_skill_comp = 2 ** n - 1\n",
    "\n",
    "        dp = {}\n",
    "        def innerSST(i, skill_comp):\n",
    "            if i == m:\n",
    "                if skill_comp == full_skill_comp: return (0, -1)\n",
    "                else: return (m + 1, -1)\n",
    "            else:\n",
    "                if skill_comp == full_skill_comp: return (0, -1)\n",
    "            \n",
    "            if dp.get((i, skill_comp)) != None:\n",
    "                return dp[(i, skill_comp)]\n",
    "            \n",
    "            min_group_size = m + 1\n",
    "            min_group_size_member = -1\n",
    "            for j in range(i, m):\n",
    "                people_skills = people[j]\n",
    "                people_skill_comp = 0\n",
    "                for skill in people_skills:\n",
    "                    skill_no = no_by_req_skill[skill]\n",
    "                    people_skill_comp = people_skill_comp + (1 << skill_no)\n",
    "                next_skill_comp = skill_comp | people_skill_comp\n",
    "                partial = innerSST(j + 1, next_skill_comp)\n",
    "                dp[(j + 1, next_skill_comp)] = partial\n",
    "                group_size, next_member = partial\n",
    "                if group_size + 1 < min_group_size:\n",
    "                    min_group_size = group_size + 1\n",
    "                    min_group_size_member = j\n",
    "            \n",
    "            return (min_group_size, min_group_size_member)\n",
    "        \n",
    "        group_size, member = innerSST(0, 0)\n",
    "        i = 1\n",
    "        res = [ member ]\n",
    "        member_skills = people[member]\n",
    "        skill_comp = 0\n",
    "        for skill in member_skills:\n",
    "            skill_no = no_by_req_skill[skill]\n",
    "            skill_comp = skill_comp + (1 << skill_no)\n",
    "        while i < group_size:\n",
    "            next_group_size, next_member = innerSST(member + 1, skill_comp)\n",
    "            res.append(next_member)\n",
    "            next_member_skills = people[next_member]\n",
    "            member_skill_comp = 0\n",
    "            for skill in next_member_skills:\n",
    "                skill_no = no_by_req_skill[skill]\n",
    "                member_skill_comp = member_skill_comp + (1 << skill_no)\n",
    "            skill_comp = skill_comp | member_skill_comp\n",
    "            member = next_member\n",
    "            i = i + 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        skills = {x:i for i,x in enumerate(req_skills)}\n",
    "        a = []\n",
    "        for sk in people:\n",
    "            i = 0\n",
    "            for s in sk:\n",
    "                i |= (1 << skills[s])\n",
    "            a.append(i)\n",
    "        \n",
    "        n = len(a)\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "            if i < 0:\n",
    "                return n\n",
    "            return min(dfs(i - 1,mask), dfs(i - 1,mask & ~a[i]) + 1)\n",
    "        # 如果人员长度大于64，可以这样构造答案\n",
    "        @cache\n",
    "        def make_ans(i,mask):\n",
    "            if mask == 0:\n",
    "                return []\n",
    "            res1,res2 = dfs(i - 1,mask),dfs(i - 1,mask & ~a[i])\n",
    "            if res1 <= res2:\n",
    "                return make_ans(i - 1,mask)\n",
    "            else:\n",
    "                return [i] + make_ans(i - 1,mask & ~a[i])\n",
    "        \n",
    "        return make_ans(n - 1,(1 << len(req_skills)) - 1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        m, n = len(req_skills), len(people)\n",
    "        dic = {s: i for i, s in enumerate(req_skills)}\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, state):\n",
    "            if state.bit_count() == m:\n",
    "                return 0, []\n",
    "            if idx == n:\n",
    "                return inf, []\n",
    "            \n",
    "            v, res = dfs(idx + 1, state)\n",
    "            for s in people[idx]:\n",
    "                state |= 1 << dic[s]\n",
    "            a, b = dfs(idx + 1, state)\n",
    "            a += 1\n",
    "            if a < v:\n",
    "                c = b[::]\n",
    "                c.append(idx)\n",
    "                v, res = a, c\n",
    "            return v, res\n",
    "\n",
    "        ans = dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        map0 = {skill:i for i,skill in enumerate(req_skills)}\n",
    "        n = len(req_skills)\n",
    "        N = len(people)\n",
    "        temp = []\n",
    "        debug = 0\n",
    "        for i,skills in enumerate(people):\n",
    "            if debug:\n",
    "                # print(i,skills)\n",
    "                pass\n",
    "            b = 0\n",
    "            for skill in skills:\n",
    "                b |= (1<<map0[skill])\n",
    "            temp.append(b)\n",
    "        if debug:\n",
    "            # print(map0)\n",
    "            # print(temp)\n",
    "            pass\n",
    "        rec = {0:[[]]}\n",
    "        for i,code in enumerate(temp):\n",
    "            trec = {}\n",
    "            lrec = {}\n",
    "            for pcode in rec.keys():\n",
    "                tcode = pcode | code\n",
    "                if tcode in trec:\n",
    "                    continue\n",
    "                trec[tcode] = []\n",
    "                lrec[tcode] = N+1\n",
    "            for pcode in rec.keys():\n",
    "                tcode = pcode|code\n",
    "                if lrec[tcode]<len(rec[pcode][0])+1:\n",
    "                    continue\n",
    "                if lrec[tcode] > len(rec[pcode][0])+1:\n",
    "                    trec[tcode] = []\n",
    "                lrec[tcode] = len(rec[pcode][0])+1\n",
    "                for comb in rec[pcode]:\n",
    "                    trec[tcode].append(comb+[i])\n",
    "            if debug:\n",
    "                print(i,code,trec)\n",
    "            for code in trec.keys():\n",
    "                if code not in rec:\n",
    "                    rec[code] = trec[code]\n",
    "                elif lrec[code] > len(rec[code][0]):\n",
    "                    continue\n",
    "                elif lrec[code] == len(rec[code][0]):\n",
    "                    rec[code].extend(trec[code])\n",
    "                else:\n",
    "                    rec[code] = trec[code]\n",
    "        return rec[(1<<n)-1][0]\n",
    "'''\n",
    "[\"java\",\"nodejs\",\"reactjs\"]\n",
    "[[\"java\"],[\"nodejs\"],[\"nodejs\",\"reactjs\"]]\n",
    "[\"algorithms\",\"math\",\"java\",\"reactjs\",\"csharp\",\"aws\"]\n",
    "[[\"algorithms\",\"math\",\"java\"],[\"algorithms\",\"math\",\"reactjs\"],[\"java\",\"csharp\",\"aws\"],[\"reactjs\",\"csharp\"],[\"csharp\",\"math\"],[\"aws\",\"java\"]]\n",
    "[\"iduaphsxybvsgxp\",\"xjxclompnbqqb\",\"uamgkhykkt\",\"ahjrwvmelymtw\",\"wbwvjsgesped\",\"vkumsyjlvlr\",\"jdhjxrl\",\"kvlhqgagymyp\",\"qkv\",\"zotxpvypsum\"]\n",
    "[[\"iduaphsxybvsgxp\",\"zotxpvypsum\"],[],[\"xjxclompnbqqb\",\"ahjrwvmelymtw\",\"vkumsyjlvlr\",\"qkv\"],[\"wbwvjsgesped\",\"vkumsyjlvlr\"],[\"uamgkhykkt\"],[],[\"iduaphsxybvsgxp\",\"xjxclompnbqqb\",\"jdhjxrl\"],[\"ahjrwvmelymtw\"],[\"ahjrwvmelymtw\"],[\"xjxclompnbqqb\",\"vkumsyjlvlr\",\"zotxpvypsum\"],[\"vkumsyjlvlr\"],[\"wbwvjsgesped\"],[\"xjxclompnbqqb\",\"jdhjxrl\",\"qkv\"],[\"iduaphsxybvsgxp\",\"vkumsyjlvlr\",\"qkv\"],[\"iduaphsxybvsgxp\",\"wbwvjsgesped\"],[\"iduaphsxybvsgxp\",\"uamgkhykkt\"],[],[\"xjxclompnbqqb\",\"qkv\"],[\"uamgkhykkt\",\"ahjrwvmelymtw\",\"vkumsyjlvlr\",\"jdhjxrl\",\"kvlhqgagymyp\",\"qkv\"],[\"iduaphsxybvsgxp\",\"ahjrwvmelymtw\",\"kvlhqgagymyp\"]]\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        dic = { req_skills[i]:i for i in range(len(req_skills)) }\n",
    "        nr = len(req_skills)\n",
    "        n = len(people)\n",
    "        peo = [0] * n\n",
    "\n",
    "        for i in range(n) :\n",
    "            for j in range(len(people[i])) :\n",
    "                x = dic[people[i][j]]\n",
    "                peo[i] |= (1 << x)\n",
    "\n",
    "        t = (1 << nr) - 1\n",
    "        maxA = (1 << 17) - 1\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, c) :\n",
    "            if i < 0 :\n",
    "                if c == t :\n",
    "                    return 0\n",
    "                return maxA\n",
    "            \n",
    "            nc = c | peo[i]\n",
    "            pick = dfs(i-1, nc) | (1 << (i))\n",
    "            npick = dfs(i-1, c)\n",
    "            \n",
    "            if npick.bit_count() > pick.bit_count() :\n",
    "                return pick\n",
    "            return npick\n",
    "        \n",
    "        ans = dfs(n-1, 0)\n",
    "        \n",
    "        ans_arr = []\n",
    "        bits = \"{0:b}\".format(ans)\n",
    "        c = 0\n",
    "        for i in range(len(bits)-1, -1, -1) :\n",
    "            if bits[i] == '1' :\n",
    "                ans_arr.append(c)\n",
    "            c += 1\n",
    "\n",
    "\n",
    "        return ans_arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        '''\n",
    "        观察到人和技能清单构成了一定的关系\n",
    "        人这么多吗？\n",
    "        启发式，我们压缩技能清单\n",
    "        状态个数60*2**16*  (16)\n",
    "        最好对每个人也压缩一下，不然跑不过去\n",
    "        '''\n",
    "        dic=dict()\n",
    "        for c in req_skills:\n",
    "            t=len(dic)\n",
    "            dic[c]=t\n",
    "        p=[]\n",
    "        for skill in people:\n",
    "            a=0\n",
    "            for c in skill:\n",
    "                a+=2**(dic[c])\n",
    "            p.append(a)\n",
    "        res,path=0,0\n",
    "        @cache    \n",
    "        def dfs(i:int,s:int):\n",
    "            nonlocal path,res\n",
    "            if i==-1:\n",
    "                return 0 if s==0 else (1<<n)-1\n",
    "            s1=dfs(i-1,s&~p[i])|(1<<i)\n",
    "            s2=dfs(i-1,s)\n",
    "            if s1.bit_count()<s2.bit_count():\n",
    "                return s1\n",
    "            return s2\n",
    "\n",
    "        n=len(people)\n",
    "        path=dfs(n-1,(1<<len(req_skills))-1)\n",
    "        ans=[]\n",
    "        for i in range(n):\n",
    "            if path>>i&1:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        sid = {s: i for i, s in enumerate(req_skills)}\n",
    "        n = len(people)\n",
    "        mask = [0] * n\n",
    "        for i, p in enumerate(people):\n",
    "            for s in p:\n",
    "                mask[i] |= 1 << sid[s]\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if j == 0: return 0\n",
    "            if i < 0: return (1 << n) - 1\n",
    "\n",
    "            res1 = dfs(i-1, j)\n",
    "            if j & mask[i] != 0:\n",
    "                res2 = dfs(i-1, j & ~mask[i]) | (1 << i)\n",
    "                ret = res1 if res1.bit_count() < res2.bit_count() else res2\n",
    "            else:\n",
    "                ret = res1\n",
    "            return ret\n",
    "\n",
    "        ret = dfs(n-1, (1 << len(req_skills)) - 1)\n",
    "        # print(bin(ret))\n",
    "        return [i for i in range(n) if (ret & (1 << i)) != 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    dsf定义为前i个成员，要完成s的技能组合，所需要的最少备选人员组合\n",
    "    如果当前遍历的成员i所有的技能都是已经学过的，那自然不用选这个人了，否则就可以考虑选这个人和不选这个人两种情况\n",
    "    再比较两种情况的最小值，最终递归返回的就是需要的最少人员组合之一了\n",
    "    为了方便，将最少人员组合用状态压缩的形式返回\n",
    "    其中用到了多次状压：1.每个人员拥有的技能；2.当前剩余要学习的技能；3.递归过程中得到的最少人员组合\n",
    "    '''\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        m, n = len(req_skills), len(people)\n",
    "        skills = {req_skills[i]:i for i in range(m)}\n",
    "        ps = [0] * n\n",
    "        for i in range(n):\n",
    "            for skill in people[i]:\n",
    "                ps[i] |= (1 << skills[skill])\n",
    "        \n",
    "        '''\n",
    "        1.递归的逻辑不要变成i对应的人员选择组合下，学习了s课程组合的下需要的人员，然后再判断当前递归到结束的人员数量小于暂存的答案就更新\n",
    "        这种方式是可以做的，但是时间复杂度较高，递归两个入参2^m、2^n，再加上递归内部需要遍历哪些课程没有学过又是m，总复杂度到了2^m2^n*m\n",
    "        '''\n",
    "        @cache\n",
    "        def helper(i, s):\n",
    "            '''\n",
    "            如果没有需要学习的课程了，就说明不需要人了，员工数就是0\n",
    "            '''\n",
    "            if not s:\n",
    "                return 0\n",
    "            '''\n",
    "            如果人都用完了，需要学习的课程还有，说明这种组合不可行，返回一个最大值\n",
    "            '''\n",
    "            if i < 0:\n",
    "                return (1 << n) - 1\n",
    "            \n",
    "            a = helper(i - 1, s)\n",
    "            if not s & ps[i]:\n",
    "                return a\n",
    "\n",
    "            b = helper(i - 1, s & ~ps[i]) | (1 << i)\n",
    "\n",
    "            if a.bit_count() < b.bit_count():\n",
    "                return a\n",
    "            return b\n",
    "        \n",
    "        res = helper(n - 1, (1 << m) - 1) \n",
    "        return [i for i in range(n) if res & (1 << i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "由于这个people的个数有点多，要是10个左右还可以考虑考虑状态压缩\n",
    "所以考虑用回溯算法\n",
    "'''\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "\n",
    "        sk_n = len(req_skills)\n",
    "\n",
    "        index = {req_skills[i]: i for i in range(sk_n)}\n",
    "\n",
    "        p_n = len(people)\n",
    "        #pNum[i]表示i员工会的技能（二进制表示）\n",
    "        pNum = [0] * p_n\n",
    "        for i in range(p_n):\n",
    "            for sk in people[i]:\n",
    "                pNum[i] |= 1 << index[sk]\n",
    "\n",
    "        #pNum.sort(key = lambda x: -x.bit_count())\n",
    "\n",
    "        @cache\n",
    "        def dfs(s, i):   #s表示在前面[0,i)中选了pre个员工，会了s项, s中的有效个数为s_cnt\n",
    "            if s == (1 << sk_n) - 1:\n",
    "                return (0, [])\n",
    "\n",
    "            if i == p_n:\n",
    "                return (inf, [])    \n",
    "\n",
    "            #1. 不将i加入进来\n",
    "            p1, suf1 = dfs(s, i+1)\n",
    "            if s | pNum[i] == s:\n",
    "                return (p1, suf1)\n",
    "\n",
    "            #2. 将i加进来\n",
    "            p2, suf2 = dfs(s | pNum[i], i+1)\n",
    "            if p1 < p2 + 1:\n",
    "                p, suf = (p1, suf1)\n",
    "            else:\n",
    "                p = p2 + 1\n",
    "                suf = [i]\n",
    "                suf.extend(suf2)\n",
    "\n",
    "            return (p, suf)\n",
    "\n",
    "        return dfs(0, 0)[1]\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        skills = {x:y for y,x in enumerate(req_skills)}\n",
    "        cnt = 0\n",
    "        n = len(people)\n",
    "        val = []\n",
    "        for each in people:\n",
    "            v = 0\n",
    "            for ch in each:\n",
    "                if ch in skills:\n",
    "                    v |= 1<<skills[ch]\n",
    "            val.append(v)\n",
    "        full = (1<<len(people))-1\n",
    "        endStatus = (1<<len(req_skills)) - 1\n",
    "        @cache\n",
    "        def dfs(cur=0,curStatus=0):\n",
    "            if curStatus == endStatus:\n",
    "                return 0\n",
    "            if cur == n:\n",
    "                return full\n",
    "            # 不选择当前成员\n",
    "            ans1 = dfs(cur+1,curStatus)\n",
    "            ans2 = full\n",
    "            # 当前成员的技能必须和当前已掌握的不重合并且当前成员的技能数值要与最终状态有重合\n",
    "            # 才可以选择\n",
    "            if curStatus&val[cur] != val[cur] and val[cur]&endStatus:\n",
    "                ans2 = dfs(cur+1,curStatus|val[cur])|(1<<cur)\n",
    "            return min(ans1,ans2,key=lambda x:bin(x).count('1'))\n",
    "        ans = dfs()\n",
    "        res = bin(ans)[2:]\n",
    "        ans = []\n",
    "        for i,j in enumerate(res[::-1]):\n",
    "            if j == '1':\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        n = len(req_skills)\n",
    "        d = {e:i for i,e in enumerate(req_skills)}\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "            if i == len(people):\n",
    "                return (1 << n) - 1\n",
    "            #不选\n",
    "            ans1 = dfs(i + 1,mask)\n",
    "            #选\n",
    "            for skill in people[i]:\n",
    "                if (mask >> d[skill]) & 1:\n",
    "                    mask ^= (1 << d[skill])\n",
    "            ans2 = dfs(i + 1,mask) | (1 << i)\n",
    "            return ans1 if ans1.bit_count() < ans2.bit_count() else ans2\n",
    "\n",
    "        ans = dfs(0,((1 << n) - 1))\n",
    "        return [i for i in range(len(people)) if (ans >> i) & 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        sid = {s: i for i, s in enumerate(req_skills)}  # 字符串映射到下标\n",
    "        n = len(people)\n",
    "        mask = [0] * n\n",
    "        for i, skills in enumerate(people):\n",
    "            for s in skills:  # 把 skills 压缩成一个二进制数 mask[i]\n",
    "                mask[i] |= 1 << sid[s]\n",
    "\n",
    "        # dfs(i,j) 表示从前 i 个集合中选择一些集合，并集等于 j，需要选择的最小集合\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if j == 0: return 0  # 背包已装满\n",
    "            if i < 0: return (1 << n) - 1  # 没法装满背包，返回全集，这样下面比较集合大小会取更小的\n",
    "            res = dfs(i - 1, j)  # 不选 mask[i]\n",
    "            res2 = dfs(i - 1, j & ~mask[i]) | (1 << i)  # 选 mask[i]\n",
    "            return res if res.bit_count() < res2.bit_count() else res2\n",
    "\n",
    "        res = dfs(n - 1, (1 << len(req_skills)) - 1)\n",
    "        return [i for i in range(n) if (res >> i) & 1]  # 所有在 res 中的下标\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "\n",
    "        m, n = len(req_skills), len(people)\n",
    "        mask_skill = dict()\n",
    "        for i, skill in enumerate(req_skills):\n",
    "            mask_skill[skill] =  i\n",
    "        \n",
    "        mask_p = [0] * n\n",
    "\n",
    "        for i, pp in enumerate(people):\n",
    "            for p in pp:\n",
    "                mask_p[i] |= (1 << mask_skill[p])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, j: int):\n",
    "            if i == n:\n",
    "                if j == (1 << m) - 1:\n",
    "                    return True, []\n",
    "                return False, []\n",
    "            \n",
    "            f11, f12 = dfs(i + 1, j)\n",
    "            f21, f22 = dfs(i + 1, j | mask_p[i])\n",
    "            \n",
    "            if not f11 and not f21:\n",
    "                return False, []\n",
    "            if not f11:\n",
    "                return True, f22 + [i]\n",
    "            if not f21:\n",
    "                return True, f12\n",
    "            \n",
    "            if len(f12) > len(f22):\n",
    "                return True, f22 + [i]\n",
    "            return True, f12 \n",
    "\n",
    "        \n",
    "        return dfs(0,0)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        di = {s:i for i,s in enumerate(req_skills)}\n",
    "        full = (1<<(len(req_skills)))-1\n",
    "        n = len(people)\n",
    "        p = [0]*n\n",
    "        for i,l in enumerate(people):\n",
    "            for s in l: p[i] |= 1<<(di[s])\n",
    "        all_people = (1<<n)-1\n",
    "\n",
    "        @cache\n",
    "        def f(i,j):\n",
    "            if j == full: return 0\n",
    "            if i == n: return all_people\n",
    "            a = f(i+1,j|p[i])|(1<<i)\n",
    "            b = f(i+1,j)\n",
    "            return a if a.bit_count() < b.bit_count() else b\n",
    "        \n",
    "        ans = f(0,0)\n",
    "        return [i for i in range(n) if ans&(1<<i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        di = {s:i for i,s in enumerate(req_skills)}\n",
    "        full = (1<<(len(req_skills)))-1\n",
    "        p = [0]*len(people)\n",
    "        for i,l in enumerate(people):\n",
    "            for s in l: p[i] |= 1<<(di[s])\n",
    "\n",
    "        @cache\n",
    "        def f(i,j):\n",
    "            if j == full: return 0\n",
    "            if i == len(p): return (1<<len(p))-1\n",
    "            a = f(i+1,j|p[i])|(1<<i)\n",
    "            b = f(i+1,j)\n",
    "            return a if a.bit_count() < b.bit_count() else b\n",
    "        \n",
    "        ans = f(0,0)\n",
    "        return [i for i in range(len(p)) if ans&(1<<i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "由于这个people的个数有点多，要是10个左右还可以考虑考虑状态压缩\n",
    "所以考虑用回溯算法\n",
    "'''\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "\n",
    "        sk_n = len(req_skills)\n",
    "\n",
    "        index = {req_skills[i]: i for i in range(sk_n)}\n",
    "\n",
    "        p_n = len(people)\n",
    "        #pNum[i]表示i员工会的技能（二进制表示）\n",
    "        pNum = [0] * p_n\n",
    "        for i in range(p_n):\n",
    "            for sk in people[i]:\n",
    "                pNum[i] |= 1 << index[sk]\n",
    "\n",
    "        @cache\n",
    "        def dfs(s, i):   #s表示在前面[0,i)中选了pre个员工，会了s项, s中的有效个数为s_cnt\n",
    "            if s == (1 << sk_n) - 1:\n",
    "                return 0\n",
    "\n",
    "            if i == p_n:\n",
    "                return (1 << p_n) - 1    \n",
    "\n",
    "            #1. 不将i加入进来\n",
    "            p1 = dfs(s, i+1)\n",
    "            if s | pNum[i] == s:   #说明将i加进来是冗余，不会带来收益\n",
    "                return p1\n",
    "\n",
    "            #2. 将i加进来\n",
    "            p2 = dfs(s | pNum[i], i+1)\n",
    "            p2 |= 1 << i\n",
    "            if p1.bit_count() < p2.bit_count():\n",
    "                p = p1\n",
    "            else:\n",
    "                p = p2\n",
    "\n",
    "            return p\n",
    "\n",
    "        vis = dfs(0, 0)\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while vis:\n",
    "            if vis & 1 > 0:\n",
    "                ans.append(i)\n",
    "            vis >>= 1    \n",
    "            i +=  1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        #copy zero\n",
    "        m = len(req_skills)\n",
    "        n = len(people)\n",
    "\n",
    "        skillindex = dict()\n",
    "        for i,skill in enumerate(req_skills):\n",
    "            skillindex[skill] = i\n",
    "        \n",
    "        personmask = [0]*n\n",
    "        for i, skills in enumerate(people):\n",
    "            for skill in skills:\n",
    "                personmask[i] |=(1<<skillindex[skill])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,skillmask):\n",
    "            if i == n :\n",
    "                if skillmask == (1<<m)-1:\n",
    "                    return True,[]\n",
    "                return False,[]\n",
    "            \n",
    "            check1,lst1 = dfs(i+1,skillmask|personmask[i])\n",
    "            check2,lst2 = dfs(i+1,skillmask)\n",
    "\n",
    "            if not check1 and not check2:\n",
    "                return False,[]\n",
    "            \n",
    "            if not check1:\n",
    "                return True,lst2\n",
    "            \n",
    "            if not check2:\n",
    "                return True,lst1+[i]\n",
    "            \n",
    "            if len(lst1) +1 <= len(lst2):\n",
    "                return True,lst1+[i]\n",
    "            else:\n",
    "                return True,lst2\n",
    "        \n",
    "        return dfs(0,0)[1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        memo = {k: v for v, k in enumerate(req_skills)}\n",
    "        @cache\n",
    "        def dfs(n, mask):\n",
    "            if mask == (1<<len(req_skills))-1:\n",
    "                return 0, []\n",
    "            if n >= len(people):\n",
    "                return float('inf'), []\n",
    "            choice = float('inf')\n",
    "            ans = []\n",
    "            new_mask = mask\n",
    "            for skill in people[n]:\n",
    "                idx = memo[skill]\n",
    "                if (mask >> idx) & 1 == 0:\n",
    "                    new_mask += (1<<idx)\n",
    "            c1, arr1 = dfs(n+1, new_mask)\n",
    "            c1 += 1\n",
    "            if c1 < choice:\n",
    "                choice = c1\n",
    "                ans = arr1 + [n]\n",
    "            c2, arr2 = dfs(n+1, mask)\n",
    "            if c2 < choice:\n",
    "                choice = c2\n",
    "                ans = arr2\n",
    "                \n",
    "            return choice, ans\n",
    "        count, ans = dfs(0,0)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "        #print(count, ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        di = {skill:i for i,skill in enumerate(req_skills)}\n",
    "        full = (1<<len(req_skills))-1\n",
    "        # p = [sum(1<<di[s] for s in pe) for pe in people]\n",
    "        p = [0]*len(people)\n",
    "        for i,pe in enumerate(people):\n",
    "            for s in pe: p[i] |= 1<<di[s]\n",
    "        all_people = (1<<len(people))-1\n",
    "\n",
    "        @cache\n",
    "        def f(i,j):\n",
    "            if j == full: return 0\n",
    "            if i == len(people): return all_people\n",
    "            a = f(i+1,j)\n",
    "            b = f(i+1,j|p[i]) | (1<<i)\n",
    "            return a if a.bit_count()<b.bit_count() else b\n",
    "        \n",
    "        ans = f(0,0)\n",
    "        return [i for i in range(len(people)) if (ans>>i) & 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        sid = {s: i for i, s in enumerate(req_skills)}\n",
    "        n = len(people)\n",
    "        mask = [0] * n\n",
    "        for i, l in enumerate(people):\n",
    "            for x in l:\n",
    "                mask[i] |= 1 << sid[x]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, j: int):\n",
    "            if j == 0: return 0\n",
    "            if i == n: return (1 << n) - 1\n",
    "            ans1 = dfs(i + 1, j)\n",
    "            ans2 = dfs(i + 1, j & ~mask[i]) | (1 << i)\n",
    "            return ans1 if ans1.bit_count() < ans2.bit_count() else ans2\n",
    "        \n",
    "        ans = dfs(0, (1 << len(req_skills)) - 1)\n",
    "        return [i for i in range(n) if ans >> i & 1 == 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "\n",
    "        book = {}\n",
    "        for i, s in enumerate(req_skills):\n",
    "            book[s] = i\n",
    "\n",
    "        n, m = len(people), len(req_skills)\n",
    "        msk = [0] * n\n",
    "        for i in range(n):\n",
    "            for s in people[i]:\n",
    "                msk[i] |= (1 << book[s])\n",
    "\n",
    "        full = 1 << m\n",
    "\n",
    "        # 状态转移：dp[i][j] = min(dp[i][j],dp[i-1][j^msk[i]]+1\n",
    "        @cache\n",
    "        def dfs(pos,state):\n",
    "            if pos==n:\n",
    "                return (1<<n)-1 if state!=full-1 else 0\n",
    "            \n",
    "            a = dfs(pos+1,state)\n",
    "            b = dfs(pos+1,state|msk[pos])|(1<<pos)\n",
    "            return a if a.bit_count() < b.bit_count() else b\n",
    "\n",
    "        ret = dfs(0,0)\n",
    "        return [i for i in range(n) if ret&(1<<i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        mapValue = dict(map(reversed, enumerate(req_skills)))\n",
    "        a = (1 << len(req_skills)) - 1\n",
    "        for i, v in enumerate(people):\n",
    "            people[i] = reduce(lambda t, i: t | (1 << int(mapValue[i])), v, 0)\n",
    "        \n",
    "        @lru_cache(maxsize=len(people) // 2 * a)\n",
    "        def dp(i, used):\n",
    "            if used == 0: return 0\n",
    "            if i < 0: return a\n",
    "\n",
    "            r1 = dp(i - 1, used)\n",
    "            r2 = dp(i - 1, used & (used ^ people[i])) \n",
    "            return r1 if r1.bit_count() < r2.bit_count() + 1 else r2 | (1 << i)\n",
    "        r = dp(len(people) - 1, a)\n",
    "        res = []\n",
    "        while r:\n",
    "            res.append((r & -r).bit_length() - 1)\n",
    "            r &= r - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        sid = {s:i for i,s in enumerate(req_skills)}\n",
    "        self.n = len(people)\n",
    "        self.mask = [0] * self.n\n",
    "        for i,skills in enumerate(people):\n",
    "            for s in skills:\n",
    "                self.mask[i] |= (1 << sid[s])\n",
    "        res = self.dfs(self.n-1, (1 << len(req_skills)) - 1)\n",
    "        return [i for i in range(self.n) if res >> i & 1]\n",
    "\n",
    "\n",
    "    \n",
    "    @cache\n",
    "    def dfs(self, i, j):\n",
    "        if j <= 0: return 0\n",
    "        if i < 0: return (1<< self.n) - 1 \n",
    "        res1 = self.dfs(i-1,j)\n",
    "        res2 = self.dfs(i-1, j&(~self.mask[i])) | (1 << i)\n",
    "        return res1 if res1.bit_count() < res2.bit_count() else res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        d=defaultdict(int)\n",
    "        for v in req_skills:\n",
    "            d[v]=len(d)\n",
    "\n",
    "        for i,v in enumerate(people):\n",
    "            t=0\n",
    "            for j in v:\n",
    "                t|=1<<d[j]\n",
    "            people[i]=t\n",
    "        \n",
    "        def count(st):\n",
    "            res=0\n",
    "            while st:\n",
    "                res+=st&1\n",
    "                st>>=1\n",
    "            return res\n",
    "        full=(1<<len(req_skills))-1\n",
    "\n",
    "        # 返回选人情况\n",
    "        @cache\n",
    "        def f(i,st2): # 从i开始选人       st2 需要的技能 0是需要的技能\n",
    "            if st2==full:\n",
    "                return  0\n",
    "            if i==len(people):\n",
    "                return (1<<len(people))-1\n",
    "\n",
    "            t1=f(i+1,st2|people[i])|(1<<i)\n",
    "            t2=f(i+1,st2)\n",
    "            return t2 if count(t1)>count(t2) else t1\n",
    "        t=f(0,0)\n",
    "        res=[]\n",
    "        i=0\n",
    "        while t:\n",
    "            if t&1:\n",
    "                res.append(i)\n",
    "            t>>=1\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    dsf定义为前i个人，学习了s的课程组合，所需要的最少人员组合\n",
    "    将当前递归所需要的最少人员在“回”的过程中计算进去\n",
    "    '''\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        m, n = len(req_skills), len(people)\n",
    "        skills = {req_skills[i]:i for i in range(m)}\n",
    "        ps = [0] * n\n",
    "        for i in range(n):\n",
    "            for skill in people[i]:\n",
    "                ps[i] |= (1 << skills[skill])\n",
    "        \n",
    "        @cache\n",
    "        def helper(i, s):\n",
    "            if s == (1 << m) - 1:\n",
    "                return 0\n",
    "            if i == n:\n",
    "                return (1 << n) - 1\n",
    "            \n",
    "            a = helper(i + 1, s | ps[i]) | (1 << i)\n",
    "            b = helper(i + 1, s)\n",
    "\n",
    "            if a.bit_count() > b.bit_count():\n",
    "                return b\n",
    "            return a\n",
    "        \n",
    "        res = helper(0, 0)\n",
    "        return [i for i in range(n) if res & (1 << i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        # 数据量小 --- 考虑DP能不能行？\n",
    "        # 首先我试了试回溯的方法 --- 超时\n",
    "        # 那就往递归的方向想\n",
    "        # 对于技能 req_skills 来说 我们可以用二进制集合的思维来考虑\n",
    "        # 将下标映射为二进制的位数\n",
    "        # skill = {v:i for i, v in enumerate(req_skills)}\n",
    "        # 我们最后要输出的方案是具体的人员方案 --- 那么我们就要对人员也进行处理\n",
    "        # 我们发现人员的数据量最大为 60 因此我们可以把人员压缩到 64 位的整数之中去\n",
    "        # 也可以看做是每个人员的技能掌握情况二进制集合\n",
    "        # n = len(people)\n",
    "        # p_skill = [0 for _ in range(n)]\n",
    "        # for i, v in enumerate(people):\n",
    "        #     for j in v:\n",
    "        #         p_skill[i] |= 1 << skill[j]\n",
    "        \n",
    "        # i 表示的是人员数  j 表示的是技能的二进制情况\n",
    "        # 边界情况 --- 当 i < 0 时表示没有人可以选 当 j == 0 时表示 所有已经填满\n",
    "        # 转移方程  ---- 类似于 0-1 背包问题\n",
    "        #                   不选                选\n",
    "        # dfs(i, j) = min(dfs(i-1, j), dfs(i-1, j & ~p_skill[i]) + 1) \n",
    "        # 但是这样求出来的最终结果是数量,没办法把得到人员的下标 --- 所以我们把下标也用二进制表示加到结果中\n",
    "        # dfs(i, j) = min(dfs(i-1, j), dfs(i-1, j & ~p_skill[i]) | (1 << i)) \n",
    "        # 这样的话求出来的最终结果就是一个人员下标的二进制表达式\n",
    "        # 要求是要选的人尽可能的少 ---- 结果的 1 尽可能的少就行了\n",
    "        # @ cache\n",
    "        # def dfs(i, j): \n",
    "        #     if j == 0: return 0 # 背包填满了\n",
    "        #     if i < 0: return (1 << n) - 1  # 选到最后发现不能满足条件 (题目是保证存在的)---- 返回最大值\n",
    "        #     # 不选\n",
    "        #     res = dfs(i - 1, j)\n",
    "        #     # 选\n",
    "        #     res2 = dfs(i - 1, j & ~ p_skill[i]) | (1 << i)\n",
    "        #     return res if res.bit_count() < res2.bit_count() else res2\n",
    "        # res = dfs(n-1, (1 << len(skill)) - 1)\n",
    "        # return [i for i in range(n) if (res >> i) & 1]\n",
    "\n",
    "        # 递归转递推\n",
    "        skill = {v:i for i, v in enumerate(req_skills)}\n",
    "        n = len(people)\n",
    "        p_skill = [0 for _ in range(n)]\n",
    "        for i, v in enumerate(people):\n",
    "            for j in v:\n",
    "                p_skill[i] |= 1 << skill[j]\n",
    "        dp = [[0] * (1 << len(skill)) for _ in range(n + 1)] \n",
    "        dp[0] = [(1 << n) - 1] * (1 << len(req_skills))\n",
    "        dp[0][0] = 0\n",
    "        # 第 i 个人是 选 还是 不选\n",
    "        for i, skills in enumerate(people, 1):\n",
    "            for j in range(1, 1 << len(skill)):\n",
    "                res = dp[i-1][j] \n",
    "                res2 = dp[i-1][j & ~p_skill[i-1]] | (1<<(i-1))\n",
    "                dp[i][j] = res if res.bit_count() < res2.bit_count() else res2\n",
    "        res = dp[-1][-1]\n",
    "        return [i for i in range(n) if (res >> i) & 1]\n",
    "\n",
    " \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        sid = {s: i for i, s in enumerate(req_skills)}  # 字符串映射到下标\n",
    "        n = len(people)\n",
    "        u = 1 << len(req_skills)\n",
    "        # f[i+1][j] 表示从前 i 个集合中选择一些集合，并集等于 j，需要选择的最小集合\n",
    "        f = [[0] * u for _ in range(n + 1)]\n",
    "        f[0] = [(1 << n) - 1] * u  # 对应记忆化搜索中的 if i < 0: return (1 << n) - 1\n",
    "        f[0][0] = 0\n",
    "        for i, skills in enumerate(people):\n",
    "            mask = 0\n",
    "            for s in skills:  # 把 skills 压缩成一个二进制数 mask\n",
    "                mask |= 1 << sid[s]\n",
    "            for j in range(1, u):\n",
    "                res = f[i][j]  # 不选 mask\n",
    "                res2 = f[i][j & ~mask] | (1 << i)  # 选 mask\n",
    "                f[i + 1][j] = res if res.bit_count() < res2.bit_count() else res2\n",
    "        res = f[-1][-1]\n",
    "        return [i for i in range(n) if (res >> i) & 1]  # 所有在 res 中的下标\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        # maps = {skill:i for i,skill in enumerate(req_skills)}  # 字符串映射到下标\n",
    "        # n = len(people)\n",
    "        # mask = [0] * n\n",
    "        # for i,skills in enumerate(people):\n",
    "        #     for s in skills:  # 把 skills 压缩成一个二进制数 mask[i]\n",
    "        #         mask[i] |= 1<<maps[s]\n",
    "        \n",
    "        # # dfs(i,j) 表示从前 i 个集合中选择一些集合，并集等于 j，需要选择的最小集合\n",
    "        # @functools.cache\n",
    "        # def dfs(i,j):\n",
    "        #     if j == 0: # 背包已装满\n",
    "        #         return 0\n",
    "        #     if i < 0:  # 没法装满背包，返回全集，这样下面比较集合大小会取更小的\n",
    "        #         return (1<<n)-1\n",
    "        #     res1 = dfs(i-1, j)  # 不选 mask[i]\n",
    "        #     res2 = dfs(i-1, j&~mask[i]) | (1<<i)  # 选 mask[i]\n",
    "        #     if res1.bit_count() < res2.bit_count():\n",
    "        #         return res1\n",
    "        #     else:\n",
    "        #         return res2\n",
    "        \n",
    "        # res = dfs(n-1, (1<<len(req_skills))-1)\n",
    "        # ans = []\n",
    "        # for i in range(n):\n",
    "        #     if (res >>i) & 1:  # 所有在 res 中的下标\n",
    "        #         ans.append(i)  \n",
    "        # return ans \n",
    "\n",
    "        maps = {skill:i for i,skill in enumerate(req_skills)}\n",
    "        n = len(people)\n",
    "        m = 1 << len(req_skills)\n",
    "        dp = [[0]*m for _ in range(n+1)]\n",
    "        for j in range(m):\n",
    "            dp[0][j] = (1<<n)-1\n",
    "        dp[0][0] = 0\n",
    "        for i,skills in enumerate(people):\n",
    "            mask = 0\n",
    "            for ski in skills:\n",
    "                mask |= 1<<maps[ski]\n",
    "            for j in range(1,m):\n",
    "                res1 = dp[i][j]\n",
    "                res2 = dp[i][j&~mask] | (1<<i)\n",
    "                if res1.bit_count() < res2.bit_count():\n",
    "                    dp[i+1][j] = res1\n",
    "                else:\n",
    "                    dp[i+1][j] = res2\n",
    "        temp = dp[-1][-1]\n",
    "        return [i for i in range(n) if (temp>>i)&1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        n = len(req_skills)\n",
    "        np = len(people)\n",
    "        di = {x:i for i, x in enumerate(req_skills)}\n",
    "        new_people = []\n",
    "        for x in people:\n",
    "            temp = 0\n",
    "            for y in x:\n",
    "                temp |= 1 << di[y]\n",
    "            new_people.append(temp)\n",
    "\n",
    "        @cache\n",
    "        def fun2(s, p):\n",
    "            if s == 0:\n",
    "                return 0, 0\n",
    "            if p == -1:\n",
    "                return 0, float('inf')\n",
    "            s1 = s & ~new_people[p]\n",
    "            p1, pn1 = fun2(s1, p - 1)\n",
    "            p1 = p1 | (1 << p)\n",
    "            pn1 += 1\n",
    "            p2, pn2 = fun2(s, p - 1)\n",
    "            if pn1 < pn2:\n",
    "                # print([bin(s), p], [bin(p1), pn1])\n",
    "                return p1, pn1\n",
    "            else:\n",
    "                # print([bin(s), p], [bin(p2), pn2])\n",
    "                return p2, pn2\n",
    "\n",
    "        p, _ = fun2((1 << n) - 1, np - 1)\n",
    "        res = [i for i in range(np) if (p >> i) & 1 == 1]\n",
    "        # print('res', bin(p), res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "\n",
    "        m = len(req_skills)\n",
    "        n = len(people)\n",
    "        d = dict()\n",
    "        for i in range(m):\n",
    "            d[req_skills[i]] = (1<<i)\n",
    "        mask = [0]*n\n",
    "        for i in range(n):\n",
    "            cur = 0\n",
    "            for skill in people[i]:\n",
    "                cur|=d[skill]\n",
    "            mask[i] = cur\n",
    "        # dp[i][j]表示前j个集合元素和等于i的最小集合\n",
    "        dp = [[2**n-1]*(n+1) for i in range(2**m)]\n",
    "        for i in range(0,n+1):\n",
    "            dp[0][i] = 0\n",
    "        for i in range(1,2**m):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j] = dp[i][j-1]\n",
    "                tmp = dp[i&~mask[j-1]][j-1]|(1<<(j-1))\n",
    "                dp[i][j] = dp[i][j-1] if dp[i][j-1].bit_count()<tmp.bit_count() else tmp\n",
    "        res =  dp[2**m-1][n]\n",
    "        return [i for i in range(n) if (res>>i)&1]\n",
    "\n",
    "        # m = len(req_skills)\n",
    "        # n = len(people)\n",
    "        # d = dict()\n",
    "        # for i in range(m):\n",
    "        #     d[req_skills[i]] = (1<<i)\n",
    "        # mask = [0]*n\n",
    "        # for i in range(n):\n",
    "        #     cur = 0\n",
    "        #     for skill in people[i]:\n",
    "        #         cur|=d[skill]\n",
    "        #     mask[i] = cur\n",
    "        # # 返回前j个集合元素和等于i的最小集合\n",
    "        # @cache\n",
    "        # def dp(i,j):\n",
    "        #     if i==0: return 0\n",
    "        #     if j<0: return 2**n-1\n",
    "        #     ans = dp(i,j-1)\n",
    "        #     tmp = dp(i&~mask[j],j-1)|(1<<j)\n",
    "        #     ans = tmp if tmp.bit_count()<ans.bit_count() else ans\n",
    "        #     return ans\n",
    "        # res = dp(2**m-1,n-1)\n",
    "        # return [i for i in range(n) if (res>>i)&1]\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        # 记忆化搜索\n",
    "        # @cache\n",
    "        # def dp(i,j):\n",
    "        #     if i==0 or j==0:\n",
    "        #         return []\n",
    "        #     ans = [k for k in range(n)]\n",
    "        #     for k in range(n):\n",
    "        #         cur = i\n",
    "        #         if ((j>>k)&1)==1:\n",
    "        #             for skill in people[k]:\n",
    "        #                 pos = d[skill]\n",
    "        #                 if ((i>>pos)&1)==1:\n",
    "        #                     cur^=(1<<pos)\n",
    "        #         if cur!=i:\n",
    "        #             tmp = [k]+dp(cur,j^(1<<k))\n",
    "        #             if len(ans)>len(tmp):\n",
    "        #                 ans = tmp\n",
    "        #     return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        # m = len(req_skills)\n",
    "        # n = len(people)\n",
    "        # d = dict()\n",
    "        # for i in range(m):\n",
    "        #     d[req_skills[i]] = i\n",
    "        # # dp(i,j)返回用j表示的可选集合构成用i表示的技能集合的最少成员编号\n",
    "        # return dp(2**m-1,2**n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        skidx = dict()\n",
    "        for i, skill in enumerate(req_skills):\n",
    "            skidx[skill] = i\n",
    "        N_skill, N_people = len(req_skills), len(people)\n",
    "        full_mask = (1 << N_skill) - 1\n",
    "        cur_masks = []\n",
    "        for p_skills in people:\n",
    "            cur = 0\n",
    "            for skill in p_skills:\n",
    "                cur |= (1 << skidx[skill])\n",
    "            cur_masks.append(full_mask - cur)\n",
    "\n",
    "        @cache\n",
    "        def get_sel(i, mask):\n",
    "            if mask == 0:\n",
    "                return 0, False\n",
    "            if i < 0:\n",
    "                return inf, False\n",
    "            min_sel, wh_pick_i = get_sel(i - 1, mask)\n",
    "            min_sel_2, wh_pick_i_2 = get_sel(i - 1, mask & cur_masks[i])\n",
    "            min_sel_2 += 1\n",
    "            if min_sel < min_sel_2:\n",
    "                return min_sel, False\n",
    "            else:\n",
    "                return min_sel_2, True\n",
    "\n",
    "        ans = []\n",
    "        mask = (1 << N_skill) - 1\n",
    "        for i in range(N_people - 1, -1, -1):\n",
    "            _, sel = get_sel(i, mask)\n",
    "            if sel:\n",
    "                mask &= cur_masks[i]\n",
    "                ans.append(i)\n",
    "            if mask == 0:\n",
    "                break\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:\n",
    "        skills = {x:y for y,x in enumerate(req_skills)}\n",
    "        cnt = 0\n",
    "        n = len(people)\n",
    "        val = []\n",
    "        for each in people:\n",
    "            v = 0\n",
    "            for ch in each:\n",
    "                v |= 1<<skills[ch]\n",
    "            val.append(v)\n",
    "        \n",
    "        endStatus = (1<<len(req_skills)) - 1\n",
    "        @cache\n",
    "        def dfs(cur=0,curStatus=0):\n",
    "            if curStatus == endStatus:\n",
    "                return 0,0\n",
    "            if cur == n:\n",
    "                return inf,0\n",
    "            cnt,ans = dfs(cur+1,curStatus)\n",
    "            if curStatus&val[cur] != val[cur] and val[cur] & endStatus:\n",
    "                c,s = dfs(cur+1,curStatus|val[cur])\n",
    "                if c + 1 < cnt:\n",
    "                    return c+1,s|(1<<cur)\n",
    "            return cnt,ans\n",
    "        _,ans = dfs()\n",
    "        return [x for x in range(n) if (1<<x)&ans]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
